문제 이해

숫자 배열이 주어진다. 아래 조건을 통해 트리를 만들 수 있다.

1. 첫 번째 정수는 트리의 루트 노드이다

2. x x+1 x+2 .. 처럼 연속된 수는 x 이전에 나왔던 수의 자식 노드이다.

3. 만약 연속되지 않은 수 y가 나왔다면, y는 자식이 없는 Node 중 가장 작은 번호를 가진 Node의 자식이 된다.

• 사촌 노드는 두 노드의 부모 노드는 다르지만, 부모의 부모 노드는 같은 Node 쌍을 말한다.

k가 주어졌을 때, k의 사촌 Node 개수를 구하는 문제이다.

---

문제 풀이

이 문제도 자식보다는 "부모"가 중요한 문제이다
Tree의 성질 중, "부모 Node 개수는 1개 이하이다"라는 특성을 활용하여 배열에 부모 Node 값을 저장하였다.
parents[tmp] = i일 경우, tmp의 부모 Node는 i가 된다.
즉, parents[자식 노드] = 부모 노드 값이 저장된다.

k가 주어지면, 부모 노드는 M = parents[k]일 것이고, 부모의 부모 노드는 N = parents[parents[k]]이 될 것이다.
즉, 모든 Node를 Search하여 부모 Node가 M은 아니지만 부모의 부모 노드가 N인 node의 개수를 찾으면 된다.

이 때 주의해야할 점은 M이나 N이 0, 즉 아무 값도 가지고 있지 않다는 의미는 k가 Root Node이거나 k의 부모 Node가 Root Node라는 의미이다.
이 경우, 부모의 부모 노드는 존재할 수 없으므로 사촌 Node의 개수는 0이라는 점을 주의하자.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N, M;
	static int[] parents;
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		while(true) {
			N = sc.nextInt();
			M = sc.nextInt();
			
			if(N==0 && M==0) break;
			
			parents = new int[N+1];
			int before = -1;
			int parent_index = -1;
			int index = 0;
			
			for(int i =1;i<=N;i++) {
                // Tree 생성 알고리즘
				int tmp = sc.nextInt();
				
				if(tmp==M) {
					index = i;
				}
				
				if(tmp-before!=1) {
					parent_index++;
				}
				parents[i] =  parent_index;
				before = tmp;
			}

			int father = parents[index]; // 부모 노드
			int ancestor = parents[father]; // 부모의 부모 노드
			
			if(father==0 || ancestor==0) { 
            // k가 Root or k의 부모가 root일 때는 0개 존재
				sb.append("0\n");
			}
			else {
				int ans = 0;
				for(int i =1;i<=N;i++) {
					if(father!=parents[i]
                             && ancestor==parents[parents[i]]) ans++;
				}
				sb.append(ans).append("\n");
			}
		}
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 3번째 메모리 초과 이유 : Node A에 부모 노드만을 저장한 것이 아닌 자식 Node의 값들까지 모두 저장시켰다. 이렇게 인접한 모든 Node들의 값을 저장하자 메모리 초과가 발생했다.

• 2번째 메모리 초과 이유 : 부모 Node가 Root이거나, k가 Root Node인 경우를 고려하지 않았다.