[백준] 2263번 트리의 순회 문제 풀어보기 : Programming Story

1. 문제

www.acmicpc.net/problem/2263

문제는 위의 링크에 들어가면 볼 수 있다.

2. 풀이

이 문제는 간단히 말해서 인오더와 포스트오더가 주어졌을때 프리오더로 출력할 수 있냐는 문제이다.

우선 트리의 순회는

https://www.programmingstory.com/2024/02/blog-post_11.html

위의 포스팅에서 다루었기 때문에 트리에 대해 처음 접하는 사람들은 위의 포스팅을 먼저 읽고 오자.

우선 인오더의 경우에는 왼쪽 자식 노드를 방문한 뒤, 루트 노드를 방문하고, 오른쪽 자식 노드를 방문하는 순서이고,

포스트오더의 경우에는 왼쪽 자식노드와 오른쪽 자식 노드를 모두 방문한 뒤 마지막에 루트 노드를 방문하는 경우를 뜻한다.

따라서 우리가 확실하게 알 수 있는 것은 포스트오더의 마지막에는 항상 루트 노드가 나온다는 것이다.

그런 다음에 인오더의 배열에서 루트 노드를 찾고, 루트 노드를 기준으로 왼쪽 자식 노드로 또 다시 재귀로 함수를 호출하고, 오른쪽 노드들로 다시 재귀함수를 호출하면 된다. 그러면서 프리오더를 구현해야 하기 때문에 루트 노드는 먼저 출력해주고, 다음에 왼쪽 자식 노드들 호출, 오른쪽 자식 노드들을 호출해주면 되는 것이다.

3. 코드

전체 코드는 아래와 같다.

import java.util.*;

public class Main{
    static int inorder[];
    static int postorder[];
    static int location[];
    static void solve(int in_s, int in_e, int post_s, int post_e ){
        if (in_s>in_e||post_s>post_e) return;
        int root=postorder[post_e];
        System.out.print(root+" ");
        int index=location[root]; //프리오더의 index
        int left_count=index-in_s; 
        solve(in_s, index-1, post_s, post_s+left_count-1);
        solve(index+1, in_e, post_s+left_count, post_e-1);
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        inorder=new int[n];
        postorder=new int[n];
        for(int i=0; i<n; i++){
            inorder[i]=sc.nextInt();
        }
        for(int i=0; i<n; i++){
            postorder[i]=sc.nextInt();
        }
        location=new int[100001];
        for(int i=0; i<n; i++){
            location[inorder[i]]=i; //숫자를 적으면 바로 index가 나오게
        }
        solve(0, n-1, 0, n-1);
    }
}

여기서 location이라는 배열을 구한 것은 매번 루트 노드가 몇 번째 index에 위치해있는지를 찾지 않기 위함이다. 그러면 시간복잡도가 매우 높게 나오기 때문에 애초에 배열을 사용해서 해당 숫자를 배열의 index로 주면 바로 몇 번째 index에 루트 노드가 위치해있는지를 판단할 수 있도록 코드를 구현했다.

solve 함수에서 in_s 는 인오더의 시작 index, in_e는 인오더의 끝 index, post_s는 포스트오더의 시작 index, post_e는 포스트오더의 끝 index를 뜻한다. 이후에 루트 노드를 찾아주고 인오더 배열 기준으로 왼쪽 오른쪽을 재귀적으로 호출해주면 프리오더를 구현할 수 있다.