codingtest

4256번 - 트리

2026-02-02
3분 분량
JAVA백준

문제 링크

문제 풀이 시간 : 27분

문제 요약

  • 이진 트리의 전위 순회(preorder) 결과와 중위 순회(inorder) 결과가 주어짐
  • 두 순회 결과로 만들어지는 트리는 항상 유일
  • 해당 트리의 후위 순회(postorder) 결과를 구하는 문제
  • 노드 개수 n ≤ 1000

문제 풀이

이 문제를 처음 봤을 때는

👉 트리를 직접 복구한 뒤, 다시 후위 순회를 하면 되겠다고 생각했다.

그래서 전위 + 중위 결과를 이용해 트리를 구성한 뒤,

후위 순회를 통해 출력하는 방식으로 접근했다.

🌳 초기 접근 – 트리를 직접 복구하기

전위 순회와 중위 순회의 특징은 다음과 같다.

  • 전위 순회: 루트 → 왼쪽 → 오른쪽
  • 중위 순회: 왼쪽 → 루트 → 오른쪽

즉,

  1. 전위 배열의 첫 번째 값은 항상 루트
  2. 중위 배열에서 해당 루트 값을 기준으로

이 구조를 재귀적으로 반복하면 트리를 복구할 수 있다.

초기 코드

java
import java.io.*;
import java.util.*;

public class Main {
	public static int[] pre, in;
	public static int n;
	public static StringBuilder sb;

	public static class Node {
		int num;
		Node left;
		Node right;

		public Node(int num) {
			this.num = num;
		}
	}

	public static Node find(int si, int ei) {
		if (si >= ei) {
			return null;
		}
		Map<Integer, Integer> s = new HashMap<>();
		for (int i = si; i < ei; i++) {
			s.put(in[i], i);
		}

		int p = -1;
		for (int i = 0; i < n; i++) {
			if (s.containsKey(pre[i])) {
				p = pre[i];
				break;
			}
		}
		Node root = new Node(p);

		root.left = find(si, s.get(p));
		root.right = find(s.get(p) + 1, ei);
		return root;
	}
	
	public static void post(Node root) {
		if(root.left!=null) {
			post(root.left);
		}
		if(root.right!=null) {
			post(root.right);
		}
		sb.append(root.num).append(" ");
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());

		for (int t = 0; t < T; t++) {
			n = Integer.parseInt(br.readLine());

			pre = new int[n];
			in = new int[n];

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++) {
				pre[i] = Integer.parseInt(st.nextToken());
			}

			int mid = -1;
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++) {
				in[i] = Integer.parseInt(st.nextToken());
				if (in[i] == pre[0]) {
					mid = i;
				}
			}

			Node root = find(0,n);
			sb = new StringBuilder();
			post(root);
			System.out.println(sb.toString());
		}
	}
}

이 방식은 논리적으로는 맞지만,

재귀 호출마다 Map을 새로 만들고,

전위 배열을 매번 처음부터 탐색하는 구조였다.

👉 즉, 시간 복잡도가 O(n2)O(n^2) 에 가까운 비효율적인 구조였다.

노드 개수가 많아지면 충분히 시간 초과가 발생할 수 있는 코드였다.

🔥 개선 아이디어

곰곰이 생각해보니,

굳이 트리를 객체로 만들 필요가 없었다.

우리가 필요한 건 트리 구조가 아니라

👉 후위 순회 결과 뿐이다.

그렇다면

  1. 전위에서 루트를 하나 꺼내고
  2. 중위에서 루트 위치를 찾아 구간을 나누고
  3. 왼쪽 → 오른쪽 재귀 호출 후
  4. 마지막에 루트를 출력하면 된다

이 방식이면 트리를 만들지 않고 바로 후위 순회 결과를 만들 수 있다.

✨ 핵심 아이디어

1️⃣ 전위 배열은 루트를 꺼내는 용도

전위 순회는 항상 루트부터 시작한다.

따라서 preIndex라는 변수를 두고

현재 서브트리의 루트를 하나씩 꺼내면 된다.

java
int rootVal = pre[preIndex++];

2️⃣ 중위 배열은 범위를 나누는 기준

중위 순회는

plain text
왼쪽 서브트리 | 루트 | 오른쪽 서브트리

구조이기 때문에,

루트의 위치를 기준으로 구간을 나눌 수 있다.

이때 루트 위치를 빠르게 찾기 위해

값 → 인덱스를 저장한 HashMap을 사용했다.

3️⃣ 후위 순서로 출력

후위 순회는

plain text
왼쪽 → 오른쪽 → 루트

이므로,

java
find(왼쪽);
find(오른쪽);
출력;

순서로 작성하면 된다.

⚙️ 시간 복잡도

  • 각 노드를 정확히 한 번씩만 방문
  • HashMap 조회는 O(1)O(1)

따라서 전체 시간 복잡도는 O(N)O(N) 이라서 초기 코드보다 훨씬 효율적인 구조이다.

최종 코드

java
import java.io.*;
import java.util.*;

public class Main {
	public static int[] pre;
	public static int n, preIndex;
	public static StringBuilder sb;
	public static Map<Integer, Integer> in;

	public static void find(int si, int ei) {
		if (si > ei)
			return;

		int rootVal = pre[preIndex++];
		int rootIdx = in.get(rootVal);

		find(si, rootIdx - 1);
		find(rootIdx + 1, ei);

		sb.append(rootVal).append(" ");
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());

		for (int t = 0; t < T; t++) {
			in = new HashMap<>();
			preIndex = 0;
			n = Integer.parseInt(br.readLine());

			pre = new int[n];

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++) {
				pre[i] = Integer.parseInt(st.nextToken());
			}

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++) {
				in.put(Integer.parseInt(st.nextToken()), i);
			}

			sb = new StringBuilder();
			find(0, n - 1);
			System.out.println(sb.toString());
		}
	}
}

함께 읽으면 좋은 글

코딩 테스트2026-04-02

5430번 - AC

함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…

코딩 테스트2026-04-02

1966번 - 프린터 큐

여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…

코딩 테스트2026-03-29

1158 - 요세푸스 문제

1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.

코딩 테스트2026-03-29

2164번 - 카드2

1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.

← 서재 목록으로 돌아가기