[백준 / BOJ] 9489 사촌

문제

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

9489번: 사촌

n명의 사람과 사촌의 수를 구해야하는 노드의 번호 k가 주어진다.

이때,  k와 사촌인 사람의 수를 구하는 문제다.

---

풀이

(뜬금없는 메모리초과가 나온문제 자바로 풀어서 그런듯?)

 

트리 구조를 만들고 탐색을 해주면 풀리는 문제이다.

 

시간복잡도는,

1. 트리구조를 만드는데 n

2. 사촌을 찾는데 n

으로 O(2n)이 되는데,  n이 최대 1000 이므로 TLE는 걱정하지 않아도된다.

 

우선, 트리구조를 만들기 위해 문제에서 트리구조를 만드는 과정을 이해해야한다.

문제에서 주어진 만드는 구조를 내가 이해한 방식대로 적어보면,

 

1. 주어진 수열에서 가장 처음나온 수는 항상 루트 노드이다.

2. 이 후, 나오는 수는 아직 자식이 없는 노드의 자식 노드가 되는데, 이때, (수열의 이전위치 수 + 1 == 수열의 현재 위치수) 라면 이 두 수는 같은 부모의 자식이 되어야한다.

 

위 방식대로 트리를 만들고, 트리의 모든 노드(총 n개가 나온다)를 탐색하며 k와 부모는 다르지만 k의 부모의 부모와는 같은 노드가 몇개인지 카운트 해주면 된다.

 

트리 만드는 코드

	private void generateTree(int parIdx, int idx){
		if(idx >= n) return;
		int node = arr[idx];
		int prevNode = arr[idx-1];
		if(prevNode+1 != node && idx > 1) parIdx++;
		tree[idx] = new Node(node, parIdx);
		generateTree(parIdx, idx+1);
	}

 

형제(k와 부모는 다르지만 k의 부모의 부모와는 같은 노드)찾는 코드

private int getSibiling(){
		int ret = 0;
		for(int idx = 1; idx < n; idx++)
			if(arr[tree[target].par] != arr[tree[idx].par] && tree[tree[target].par].par == tree[tree[idx].par].par)
            			ret++;

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/67ee7cba9f2fc272f72a1c4f82c9cdbefe5a256c/9489%20%EC%82%AC%EC%B4%8C/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃