[랜덤 마라톤] 사촌(9489)

1. 문제 풀이 아이디어

• 부모 노드의 인덱스를 배열에 저장하고, 해당 배열을 사용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        String line;
        while (!(line = bufferedReader.readLine()).startsWith("0")) {
            StringTokenizer stringTokenizer = new StringTokenizer(line);
            int n = Integer.parseInt(stringTokenizer.nextToken());
            int k = Integer.parseInt(stringTokenizer.nextToken());
            int[] c = new int[n + 1];
            int[] p = new int[n + 1];
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            p[0] = -1;
            c[0] = -1;
            int index = -1;
            int kk = 0;
            for (int i = 1; i <= n; i++) {
                c[i] = Integer.parseInt(stringTokenizer.nextToken());
                if (c[i] != c[i - 1] + 1) index++;
                if (c[i] == k) kk = i;
                p[i] = index;
            }
            int result = 0;
            for (int i = 1; i <= n; i++) {
                if (p[p[i]] != p[p[kk]])
                    continue;
                if (p[i] == p[kk])
                    continue;
                result++;
            }
            stringBuilder.append(result).append('\n');
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }
}

3. 정리

• 노드의 값을 저장할 배열 c와 부모의 인덱스를 저장할 배열 p를 n+1 크기로 정의한다.

• p[0]과 c[0]을 -1로 초기화하여 루트 노드를 설정하고, index를 -1로 초기화하여 첫 번째 노드의 부모 인덱스가 0이 되도록 한다.

• 입력을 받을 때, 값이 이전 노드 + 1이 아니라면 index를 증가시키고, 값이 k와 같으면 해당 노드의 인덱스를 kk에 저장한다.

• 입력을 모두 받은 후, p 배열을 1부터 순회하여 부모의 부모가 다르거나 부모가 같으면 건너뛰고, 그 외의 경우에는 결과값을 증가시켜 사촌의 수를 구한다.