접근

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

 

4256번: 트리

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음

www.acmicpc.net

전위 순회, 중위 순회가 주어진 트리를 후위 순회 방식으로 표시하는 문제였습니다.

전위 순회의 경우 트리에서 루트 노드를 가장 먼저 표시합니다. 이 점을 이용하여 다음과 같이 재귀적으로 문제를 해결할 수 있습니다.

  1. 전위 순회에서 가장 앞의 숫자를 꺼냅니다.
  2. 꺼내진 숫자를 중위 순회에서 찾습니다. 해당 인덱스를 기준으로 앞쪽은 왼쪽 자식 중위 순회, 뒤쪽은 오른쪽 자식 중위 순회입니다.
  3. 전위 순회의 다음 숫자를 꺼내면, 다시한번 이 숫자를 앞에서 구한 왼쪽 자식 중위 순회에서 찾습니다.

찾는 과정을 모두 거치고, 맨 처음에 꺼낸 숫자를 맨 뒤에 붙여주면 후위 순회 순서대로 배열이 완성됩니다.

코드

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

public class Main {

  static int T, n;
  static int[] preorder, inorder;
  static LinkedList<Integer> backorder;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    T = Integer.parseInt(br.readLine());
    StringBuilder sb = new StringBuilder();
    for (int t = 0; t < T; t++) {
      n = Integer.parseInt(br.readLine());
      preorder = new int[n + 1];
      inorder = new int[n + 1];
      backorder = new LinkedList<>();
      StringTokenizer st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) {
        preorder[i] = Integer.parseInt(st.nextToken());
      }
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) {
        inorder[i] = Integer.parseInt(st.nextToken());
      }
      makeBackorder(0, 0, n);
      for (int i = 0; i < n; i++) {
        sb.append(backorder.poll()).append(' ');
      }
      sb.append('\n');
    }
    br.close();
    System.out.print(sb.toString());
  }

  static void makeBackorder(int rootIdx, int s, int e) {
    int root = preorder[rootIdx];
    for (int i = s; i < e; i++) {
      if (inorder[i] == root) {
        makeBackorder(rootIdx + 1, s, i);
        makeBackorder(rootIdx + i + 1 - s, i + 1, e);
        backorder.add(root);
      }
    }
  }
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!

반응형

'코딩 > 백준 (JAVA)' 카테고리의 다른 글

백준 11967번: 불켜기 (Java)  (0) 2022.08.21
백준 2638번: 치즈 (Java)  (0) 2022.08.17
백준 2632번: 피자판매 (Java)  (0) 2022.08.15
백준 18428번: 감시 피하기 (Java)  (0) 2022.08.14
백준 3109번: 빵집 (Java)  (0) 2022.08.13
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기