728x90
성능 요약
메모리: 69800 KB, 시간: 428 ms
분류
분할 정복(divide_and_conquer), 재귀(recursion), 트리(trees)
문제 설명
n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.
출력
첫째 줄에 프리오더를 출력한다.
4256 문제랑 비슷한 것 같았는데 조금 더 까다로운 것 같다
postOrder에서 왼쪽으로 가는 것을 구현하는 것은 어렵지 않았는데, 오른쪽으로 가는 경우 inOrder과 postOrder의 index가 어긋나서 이를 처리하는 것에 시간을 많이 들였다.
다른 코드를 보니까 아예 두 index를 분리해서 순회를 계속하는 방법도 있었는데, 나는 오른쪽으로 가는 경우 cnt를 1씩 증가시키면서 index를 조정하였다.
postOrder에서 가장 오른쪽에 있는 index는 root의 index이다.
그리고 왼쪽은 inOrder의 rootIndex(mid)기준으로 왼쪽에, 오른쪽은 그 오른쪽에 있는 원소다.
계속 왼쪽으로 갈 경우에는 문제가 없지만, 한 번 오른쪽으로 갔다가 왼쪽으로 가는 경우 postOrder의 right index를 cnt만큼 감소시켜줘야 한다.
package Gold.g2;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ_2263_트리순회 {
static int[] in;
static int[] post;
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
in = new int[N + 1];
post = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
in[Integer.parseInt(st.nextToken())] = i;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
post[i] = Integer.parseInt(st.nextToken());
preOrder(0, N - 1, 0);
System.out.println(sb.toString());
}
static StringBuilder sb = new StringBuilder();
static void preOrder(int left, int right, int cnt) {
// cnt는 오른쪽으로 간 횟수
if (left > right)
return;
int root = post[right];
int mid = 0; // in에서 root의 index
mid = in[root];
sb.append(root + " ");
preOrder(left, mid - 1 - cnt, cnt);
preOrder(mid - cnt, right - 1, cnt + 1);
}
}
728x90
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 7576 - 토마토 (자바/Java) (0) | 2022.09.14 |
---|---|
[백준] 2667 - 단지 번호 붙이기 (자바/Java) (0) | 2022.09.13 |
[백준] 4803 - 트리 (자바/Java) (0) | 2022.09.12 |
[백준] 1167 - 트리의 지름 (자바/Java) (0) | 2022.09.09 |
[백준] 1300 - K번째 수 (자바/Java) (0) | 2022.09.07 |