9489번: 사촌

https://www.acmicpc.net/problem/9489

문제

증가하는 정수 수열을 이용해서 트리를 만드는 방법은 다음과 같다.

• 첫 번째 정수는 트리의 루트 노드이다.
• 다음에 등장하는 연속된 수의 집합은 루트의 자식을 나타낸다. 이 집합에 포함되는 수의 첫 번째 수는 항상 루트 노드+1보다 크다.
• 그 다음부터는 모든 연속된 수의 집합은 아직 자식이 없는 노드의 자식이 된다. 그러한 노드가 여러 가지 인 경우에는 가장 작은 수를 가지는 노드의 자식이 된다.
• 집합은 수가 연속하지 않는 곳에서 구분된다.

예를 들어, 수열 1 3 4 5 8 9 15 30 31 32를 위의 규칙을 이용해 트리를 만들면 아래 그림과 같이 된다.

두 노드의 부모는 다르지만, 두 부모가 형제(sibling)일 때 두 노드를 사촌이라고 한다.

수열 특정 노드 번호 k가 주어졌을 때, k의 사촌의 수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000)

다음 줄에는 총 n개의 수가 주어지며, 모든 수는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

입력으로 주어지는 수열은 항상 증가한다. k는 항상 수열에 포함되는 수이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스 마다, k의 사촌의 수를 출력한다.

예제 입력 1

10 15
1 3 4 5 8 9 15 30 31 32
12 9
3 5 6 8 9 10 13 15 16 22 23 25
10 4
1 3 4 5 8 9 15 30 31 32
0 0

예제 출력 1

5
1
0

풀이

package tree;

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

public class Main_9489 {

    private static int numberOfNode;
    private static int targetNode;
    private static int[] nodes;
    private static int[] parent;
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        while (true) {
            input();

            if (numberOfNode == 0 && targetNode == 0) {
                break;
            }

            process();
        }

        output();
    }

    private static void input() throws IOException {
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        numberOfNode = Integer.parseInt(st.nextToken());
        targetNode = Integer.parseInt(st.nextToken());

        if (numberOfNode == 0 && targetNode == 0) {
            return;
        }

        nodes = new int[numberOfNode];
        parent = new int[numberOfNode];

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

    }

    private static void process() {
        int result = 0;

        updateParent();

        int targetNodeIndex = getTargetNodeIndex();
        int parentIndex = parent[targetNodeIndex];

        if (parentIndex == -1 || parentIndex == 0) {
            sb.append(0).append('\n');
            return;
        }

        int grandParentIndex = parent[parentIndex];

        for (int i = 1; i < numberOfNode; i++) {
            if (parent[i] != parentIndex && parent[parent[i]] == grandParentIndex) {
                result++;
            }
        }

        sb.append(result).append('\n');
    }

    private static int getTargetNodeIndex() {
        int result = 0;

        for (int i = 1; i < numberOfNode; i++) {
            if (nodes[i] == targetNode) {
                result = i;
            }
        }

        return result;
    }

    private static void updateParent() {
        int nextNode = nodes[0] + 1;
        int parentIndex = -1;

        parent[0] = -1;

        for (int i = 1; i < numberOfNode; i++) {
            int node = nodes[i];

            if (node != nextNode) {
                parentIndex++;
                parent[i] = parentIndex;
                nextNode = node + 1;
            } else {
                parent[i] = parentIndex;
                nextNode++;
            }
        }
    }

    private static void output() {
        System.out.println(sb);
    }

}