[백준/JAVA] 2263_트리의 순회

백준🔗

2263번: 트리의 순회

 

 

 

문제

 

 

 

간단 풀이

★★ 재귀로 배열, 리스트 등을 쪼개야 할 때는 그 배열, 리스트에 직접 remove, slice 등을 해서 넘기지 말고, index를 넘겨서 관리하자!!

 

중위 LVR

후위 LRV

=> 전위 VLR

1) 후위 순회에서 가장 뒤에 있는 V 일단 출력

2) 앞에서 찾은 숫자를 중위에서 찾으면 그곳을 기준으로 왼쪽은 L, 오른쪽은 R

3) 재귀를 통해 중위와 후위에 해당하는 L, R을 넘겨서 크기가 1일 때까지 수행

 

어제의 문제와 비슷하게 접근을 했다. 아이디어 자체는 맞았지만..

처음 접근 때는 재귀에서 리스트 자체를 가지고 그 안에서 remove를 하면서 계속 들고다니려 했기 때문에 여러 에러가 발생했다. (ConcurrentModificationException이라는 예외 이번 문제에서 처음 봤다..😧)

처음에는 이런 에러를 리스트의 복사본을 만들고.. 등등의 방법으로 해결해보려 했지만..

 

코드와 헤어질 결심해서 싹 지우고 인덱스를 들고다니는 방법을 바꿨다. 오늘의 교훈. 재귀에서는 배열, 리스트 들고다니지 말고 인덱스 들고 다니면서 관리하자!!

 

이렇게 해서 되는 듯 했으나.. 시간 초과 발생.

리스트에서 숫자를 찾는 과정이 시간이 걸리는 듯 해서 배열로 자료구조를 바꿔 주었더니 시간초과 해결됐다..!!

리스트에서 indexOf, get 메서드의 시간 복잡도가 얼마나 되는건지.. 나중에 찾아보는걸루.....

 

 

테케가 부족해서 내가 만들어서 사용한 테케

 

중위 : 4 2 5 1 6 3 7

 

후위 : 4 5 2 6 7 3 1

 

전위 : 1 2 4 5 3 6 7

 

             1

          /     \

        2       3

      /    \    /    \

    4     5  6     7 

 

 

코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	static StringBuilder sb = new StringBuilder();
//	static List<Integer> in = new ArrayList<>();
//	static List<Integer> post = new ArrayList<>();
	static int[] in;
	static int[] inIdx;
	static int[] post;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt(); // 정점 개수

		in = new int[N + 1];
		inIdx = new int[N + 1];
		post = new int[N + 1];

		// 중위순회 입력받기
		for (int i = 1; i <= N; i++) {
//			in.add(sc.nextInt());
			in[i] = sc.nextInt();
			inIdx[in[i]] = i;
		}

		// 후위순회 입력받기
		for (int i = 1; i <= N; i++) {
//			post.add(sc.nextInt());
			post[i] = sc.nextInt();
		}

		traverse(1, N + 1, 1, N + 1);

		System.out.println(sb);
	}

	// from인덱스 ~ to인덱스-1 까지 포함!
	private static void traverse(int inFromIdx, int inToIdx, int postFromIdx, int postToIdx) {
		// 기저 조건
		if (inFromIdx >= inToIdx) {
			return;
		}

		// 유도 조건
		// V
		sb.append(post[postToIdx - 1] + " ");
//		sb.append(post.get(postToIdx - 1) + " ");

		// L
//		int idx = in.indexOf(post.get(postToIdx - 1));
		int idx = inIdx[post[postToIdx - 1]];
		int L_length = idx - inFromIdx;
		traverse(inFromIdx, idx, postFromIdx, postFromIdx + L_length);

		// R
		traverse(idx + 1, inToIdx, postFromIdx + L_length, postToIdx - 1);
	}
}

 

 

참고 자료

[백준] 2263 트리의 순회 - JAVA