9934번: 완전 이진 트리
상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래
www.acmicpc.net
0. 완전 이진 트리를 중위 순회한 결과가 주어졌을때, 원래의 트리를 복원하는 문제
1. 완전 이진 트리의 특성상, 왼쪽 subtree와 오른쪽 subtree의 크기가 동일하다
- 중위 순회는 왼쪽 - 자신 - 오른쪽 순서로 이루어지므로, 정 가운데 번호가 항상 root노드이다
2. 시작-끝 값으로 subtree 정보를 유지하면서, 가운데(root) 정보를 저장하며 재귀를 진행한다
- 재귀의 깊이에 따라 각 list에 저장
- subtree의 크기가 0이되면 종료한다
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = pint(br.readLine());
int[] node = new int[(int)Math.pow(2, N)-1];
ArrayList<LinkedList<Integer>> list = new ArrayList<>();
for(int i=0; i<N; i++) {
list.add(new LinkedList<>());
}
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < node.length; i++) {
node[i]=pint(st.nextToken());
}
rec(list, node, 0, node.length, 0);
for(int i=0; i<N; i++) {
for(Integer e : list.get(i)) {
System.out.print(e+" ");
}System.out.println();
}
}
static void rec(ArrayList<LinkedList<Integer>> list, int[] node,
int fst, int lst, int depth) {
if(fst==lst)return;
int mid = (fst+lst)/2;
list.get(depth).add(node[mid]);
rec(list, node, fst, mid, depth+1);//left
rec(list, node, mid+1, lst, depth+1);//right
}
static int pint(String s) {
return Integer.parseInt(s);
}
}
'알고리즘 문제 풀이 > BOJ 실버' 카테고리의 다른 글
| [백준] 1743 - 음식물 피하기 (0) | 2022.01.16 |
|---|---|
| [백준] 15900 - 나무 탈출 (0) | 2021.12.25 |
| [백준] 18428 - 감시 피하기 (1) | 2021.12.25 |
| [백준] 14496 - 그대, 그머가 되어 (0) | 2021.11.14 |
| [백준] 2346 - 풍선 터뜨리기 (0) | 2021.10.25 |
| [백준] 17276 - 배열 돌리기 (0) | 2021.10.10 |
| [백준] 1325 - 효율적인 해킹 (0) | 2021.09.25 |
