[코드트리]행복한 수열의 개수

완전탐색 문제이다.

이 문제를 어떻게 접근해야 할지 고민한 부분은 어떻게 시간복잡도를 최소한으로 줄일지였다. 결국 첫번째엔 행을 기준으로, 두번째엔 열을 기준으로 2중 for문을 2번 돌려서 풀기로 결정했다. 시간복잡도는 O(n^2)이다.

 

풀면서 고심한 부분은 변수 before와 current를 어떻게 설정할지였다. 

결국 이렇게 코드를 짰다.

처음 시도에서 통과하지 못했는데 행렬 크기가 1 x 1이고 M이 1인 경우에서 통과하지 못했다. 왜냐하면 처음엔 2중 for문의 조건식에 i와 j를 0이 아닌 1부터 시작하도록 했기 때문이다. 이 부분은 before와 current변수를 어떻게 설정할지와도 관련이 있다. 위의 코드는 그 부분까지 고려해서 코드를 짠 결과다. 

 

 

전체 코드는 다음과 같다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] NM = br.readLine().split(" ");
        int N = Integer.parseInt(NM[0]);
        int M = Integer.parseInt(NM[1]);
        int[][] arr2d = new int[N][N];
        int countOfSequence = 0;
        for(int i = 0; i < N; i++){
            String[] temp = br.readLine().split(" ");
            for(int j = 0; j < N; j++){
                arr2d[i][j] = Integer.parseInt(temp[j]);
            }
        }

//행을 기준으로 한 행복한 수열 개수 구하는 for문
        for(int i = 0; i < N; i++){
            int before = 0;
            int current = 0;
            int countedNumber = 1;
            current = arr2d[i][0];
            for(int j = 0; j < N; j++){
                if(j > 0) before = current;
                current = arr2d[i][j];
                countedNumber += (before == current) ? 1 : 0;
                if(current != before){
                    if(countedNumber >= M){
                        countOfSequence += 1;
                        break;
                    }
                    else
                        countedNumber = 1;
                }
            if(j == N-1 && countedNumber >= M && current == before)
                countOfSequence += 1;    
            }
            
        }

//열을 기준으로 한 행복한 수열의 개수를 구하는 for문
        for(int i = 0; i < N; i++){
            int before = 0;
            int current = 0;
            int countedNumber = 1;
            current = arr2d[0][i];
            for(int j = 0; j < N; j++){
                if(j > 0) before = current;
                current = arr2d[j][i];
                countedNumber += (before == current) ? 1 : 0;
                if(current != before){
                    if(countedNumber >= M){
                        countOfSequence += 1;
                        break;
                    }
                    else
                        countedNumber = 1;
                }
            if(j == N-1 && countedNumber >= M && current == before)
                countOfSequence += 1;    
            }
            
        }

        System.out.println(countOfSequence);
    }
}

 

지금처럼 예외처리를 위해 조건문이 많이 생길땐 항상 더 쉽게, 그리고 직관적으로 코드를 짤 수 있는 방법이 있다고 생각한다. 지금까지 코딩테스트 문제를 풀어오면서 다른 사람이 짠 더 단순한 코드를 볼때마다 그런 믿음이 쌓였던거 같다. 이번 문제도 다른 사람들은 어떻게 코드를 짰는지 살펴봐야겠다.