[백준BOJ] 2263번 트리의 순회.java

 

백준 저지에서 트리의 순회를 자바를 통해 풀어 보았다. 

 

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

2263번: 트리의 순회

 

2263번 트리의 순회.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

2263번 트리의 순회

문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

설명

오랜만에 정말 골치 아픈 문제를 풀었다. 처음 문제를 봤을 때는 문제 해결에 필요한 아이디어를 떠올리기 힘들어서 골드 3인가 했는데 최적화가 어려워서였다. 

 

처음에는 트리의 원래 모습을 찾는데 중점을 두었다. 포스트 오더의 마지막 인덱스는 부모 노드이며 해당 숫자를 기준으로 인 오더에서 양쪽으로 나누면 각각 왼쪽 자식과 오른쪽 자식이다. 이 과정을 재귀 함수를 통해 반복하면 트리의 원래 모습은 쉽게 찾을 수 있다. 트리의 원래 모습을 찾은 후 프리오더를 통해 각 노드들을 출력했는데 당연하게도 메모리 초과가 떴다. 그리고 엄청나게 많은 일들이 있었다.

이 과정 자체가 메모리 최적화하는 데 있어 많은 공부가 된 것 같아서 과정들을 조금씩 기록해 보겠다. 

 

우선 트리를 구현할 때 실제 노드를 바탕으로 이진트리를 직접 만들었다. 그리고 한 깊이마다 왼쪽 자식과 오른쪽 자식을 잘라내어 새로운 배열을 생성하였고 이렇게 만든 새로운 인 오더와 포스트오더 배열을 재귀 함수로 넘겨주었다. 한 번의 재귀함수마다 4개의 배열을 새로 생성하기 때문에 엄청난 메모리를 차지하게 된다. 배열을 생성하지 않고 값만 알 수 있도록 넘겨주기 위해 최초의 인오더와 포스트오더를 static으로 선언하고 재귀함수로 넘겨줄 때는 각 배열의 시작 인덱스와 끝 인덱스만 넘겨주었다. 추가로 시작 인덱스와 끝 인덱스만 넘겨주는 게 직관적으로 이해하기 어려워서 디버깅만 한 시간을 넘게 했다. 포스트 오더의 인덱스를 계산하는게 어렵기 때문인데 포스트오더의 끝 인덱스를 따로 구하려고 하지 않고 시작 인덱스에서 인 오더의 길이만큼 더해준 게 끝 인덱스라는 것을 깨달으면 이해하기가 훨씬 편해진다.

 

다음으로 실제 트리를 만들 필요가 없다는 것을 알아냈다. 프리오더란 현재 노드를 먼저 출력하고 왼쪽 자식과 오른쪽 자식을 출력하는 것인데 재귀 함수 자체가 각 배열에서 부모 노드를 구하는 것이고 왼쪽, 오른쪽 순으로 재귀함수를 돌려주면 자연스럽게 프리오더로 출력할 수 있다. 사실 그 전에 자료구조를 트리로 만든게 문제인가 싶어서 배열로도 트리를 구현해봤는데 여전히 메모리 초과가 떠서 알게 되었다.

 

추가로 각 재귀마다 부모 노드를 구하기 위해 반복문을 돌게되면 너무 오랜 시간이 걸린다. 처음 인오더를 입력받을 때 부모노드를 따로 저장해놓으면 시간을 매우 많이 줄일 수 있다.

 

 

코드

//2263번 트리의 순회.java
package week7;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 트리의_순회_2263  {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
       
    static int[] inOrder;
    static int[] postOrder;
    static int[] inOrderP;
    public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());
		
		inOrder = new int[N+1];
		postOrder = new int[N+1];
		inOrderP = new int[N+1];
		st = new StringTokenizer(br.readLine()," ");
		for(int i=0;i<N;i++) {
			inOrder[i]=Integer.parseInt(st.nextToken());
			inOrderP[inOrder[i]]=i;
		}
		st = new StringTokenizer(br.readLine()," ");
		for(int i=0;i<N;i++)postOrder[i]=Integer.parseInt(st.nextToken());
		
		preOrder(0,N,0,N);
	}
    public static void preOrder(int startI, int endI, int startP, int endP) {
    	if(startI >= endI || startP >= endP)return;
    	int p = postOrder[endP-1];
    	int index=inOrderP[p];
    	System.out.print(p+" "); //부모 출력
    	preOrder(startI,index,startP,startP+(index-startI));
    	preOrder(index+1,endI,index-startI+startP,endP-1);
    }
}