[완전탐색/자바] 코드트리 IL. 행복한 수열의 개수

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제 분석

이 문제는 n이 100까지이므로 충분히 완전탐색이 가능하다. for loop을 이용하여 손쉽게 모든 경우의 수를 훑어서 정답을 찾아낼 수 있다.

 

문제 로직

• 대각선은 훑지 않아도 되고, 가로 또는 세로만 훑으면 되므로 원래 배열, 축 반전 배열 두 가지로 저장해두고 한번에 가로와 세로를 훑을 수 있도록 하였다.
• 또한 m이 1일 때에는 비교문 연산이 필요없이 모든 행/열이 '행복한 수열'이므로 해당 부분은 별도로 처리해주었다.
• 연속성이 중간에 끊기면 카운트를 다시 하되, 한번이라도 연속성을 가진 행/열에 대해서는 '행복한 수열'임을 저장할 수 있도록 cnt 변수와 boolean변수를 활용하였다.
• 행복한 수열 개수는 ans에 저장하여 출력해 주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static int n, m, ans;
    private static int[][] arr1;
    private static int[][] arr2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr1 = new int[n][n];
        arr2 = new int[n][n];
        ans = 0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int num = Integer.parseInt(st.nextToken());
                arr1[i][j] = num;
                arr2[j][i] = num;
            }
        }
        if (m == 1) {
            ans = n * 2;
        } else {
            for (int i = 0; i < n; i++) {
                int isInARowCnt1 = 0;
                int isInARowCnt2 = 0;
                boolean isInARow1 = false;
                boolean isInARow2 = false;

                for (int j = 1; j < n; j++) {
                    if (arr1[i][j] == arr1[i][j-1]) {
                        isInARowCnt1 += (isInARowCnt1 == 0) ? 2 : 1;
                    } else {
                        isInARowCnt1 = 0;
                    }
                    if (isInARowCnt1 >= m) {
                        isInARow1 = true;
                    }
                    if (arr2[i][j] == arr2[i][j - 1]) {
                        isInARowCnt2 += (isInARowCnt2 == 0) ? 2 : 1;
                    } else {
                        isInARowCnt2 = 0;
                    }
                    if (isInARowCnt2 >= m) {
                        isInARow2 = true;
                    }
                }
                if (isInARow1) {
                    ans++;
                }
                if (isInARow2) {
                    ans++;
                }
            }
        }
        System.out.println(ans);

    }
}