백준 2263번: 트리의 순회 (Java)

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

2263번: 트리의 순회

 

 

 

 

 

 

 

 

---

 

풀이

preorder는 VLR 순으로 트리의 노드를 출력하므로, 우리는 V를 찾고, L을 찾아 L에서 V를 찾고.... R에서 V를 찾으면 됩니다.

inorder가 LVR, postorder는 LRV 순으로 트리의 노드를 출력하므로, 일단 postorder 배열의 끝 값은 노드가 됩니다. 모든 노드의 값은 중복이 없으므로, inorder 배열에서 V를 찾아준 후, 해당 위치를 기준으로 L, R을 나누어 재귀적으로 V를 찾으면 됩니다.

각 subtree의 위치를 'inorder의 시작, 끝 위치'를 저장하는 is, ie와, 'postorder의 시작, 끝 위치'를 저장하는 ps, pe라는 총 4개의 변수로 지정하도록 합니다.

마지막으로, inorder 배열에서 V를 찾는 과정을 O(1)에 수행할 수 있도록 합니다. 본 문제에서는 시간 초과가 발생하진 않지만, N= 10만이고, inorder = postorder = '1 2 3 4 ... 100000'과 같은 케이스를 생각해보면, 만약 naive한 for문으로 V를 찾으면 총 50억번의 for문 연산이 수행됩니다.

 

트리는 워낙 성질이 많다보니, 트리 문제도 보면 알고리즘을 빡세게 쓴다기보단 특정 통찰을 (대부분 재귀적으로) 구현하는 문제가 많은 듯합니다. 배우는 느낌이 좀 덜해요 :(

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int[] pre, inIdx, post;
    static int idx = 0;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        pre = new int[n+1];
        // inorder 각 노드의 등장 순서를 저장하는 배열
        inIdx = new int[n+1];
        post = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            inIdx[Integer.parseInt(st.nextToken())] = i;
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            post[i] = Integer.parseInt(st.nextToken());
        }
        
        getPreOrder(0, n-1, 0, n-1);
        System.out.println(sb.toString());
    }
 
    public static void getPreOrder(int is, int ie, int ps, int pe) {
        if (is <= ie && ps <= pe) {
            sb.append(post[pe]+ " "); 
            
            // pos: inorder에서 root의 위치
            int pos = inIdx[post[pe]];
 
            getPreOrder(is, pos - 1, ps, ps + pos - is - 1);
            getPreOrder(pos + 1, ie, ps + pos - is, pe - 1);
        }
    }
}