[Algorithm/Java] SWEA 1979번 - 어디에 단어가 들어갈 수 있을까

---

1979. 어디에 단어가 들어갈 수 있을까

---

🔍 문제 풀이

문제 도식화

끝에서 체크하는 방법이 제일 간편한 것 같다.

💻 전체 코드

[방법 1] 끝에서 체크

import java.io.*;
import java.util.*;

public class Solution {
    static int[][] arr;
    static int n, k;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= t; tc++) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            arr = new int[n][n];
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            int ans = solve();
            System.out.println("#" + tc + " " + ans);


        }
    }

    static int solve(){
        int ans = 0;

        // 가로 검사
        for (int i = 0; i < n; i++) {
            int len = 0;
            for (int j = 0; j < n; j++) {
                if(arr[i][j] == 1) len ++; // 1이면 연속 증가
                else{ // 0 만나면 끊김
                    if(len == k) ans ++;// 지금까지 누적한 게 정확히 k칸?
                    len = 0; // 초기화
                }
            }
            if(len == k) ans ++; // 마지막 구간 처리
        }


        // 세로 검사
        for (int i = 0; i < n; i++) {
            int len = 0;
            for (int j = 0; j < n; j++) {
                if(arr[j][i] == 1) len ++;
                else{
                    if(len == k) ans ++;
                    len = 0;
                }
            }
            if(len == k) ans ++;
        }


        return ans;
    }
}

[방법 2] 시작점에서 체크

static int solve() {
    int ans = 0;

    // 가로 검사
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == 1 && (j == 0 || arr[i][j - 1] == 0)) {
                int idx = j, len = 0;

                while (idx < n && arr[i][idx] == 1) {
                    len++;
                    idx++;
                }

                if (len == k) ans++;
            }
        }
    }

    // 세로 검사
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == 1 && (i == 0 || arr[i - 1][j] == 0)) {
                int idx = i, len = 0;

                while (idx < n && arr[idx][j] == 1) {
                    len++;
                    idx++;
                }

                if (len == k) ans++;
            }
        }
    }

    return ans;
}

[방법 3] 끝점 체크 + 패딩

import java.io.*;
import java.util.*;

public class Solution {
    static int[][] arr;
    static int n, k;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= t; tc++) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            arr = new int[n+1][n+1]; // 오른쪽, 아래 패딩 추가
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            int ans = solve();
            System.out.println("#" + tc + " " + ans);


        }
    }

    static int solve(){
        int ans = 0;

        // 가로 검사
        for (int i = 0; i < n; i++) {
            int len = 0;
            for (int j = 0; j <= n; j++) { // n까지
                if(arr[i][j] == 1) len ++;
                else{
                    if(len == k) ans ++;
                    len = 0;
                }
            }
            // if(len == k) ans ++; // 마지막 구간 처리 생략
        }


        // 세로 검사
        for (int i = 0; i < n; i++) {
            int len = 0;
            for (int j = 0; j <= n; j++) { // n까지
                if(arr[j][i] == 1) len ++;
                else{
                    if(len == k) ans ++;
                    len = 0;
                }
            }
            // if(len == k) ans ++; // 마지막 구간 처리 생략
        }


        return ans;
    }
}