백준 4256 JAVA

문제 유형

• 트리

문제 접근

• 답
  • 후위 순회 출력
• 주어지는 정보
  • 트리 노드 개수 최대 1000
  • 이진 트리
• 알고리즘 후보
  • 없음
  • 전위, 중위 순회로 트리의 모양을 유추 할 수 있는지를 묻는 문제 같음
• 풀이
  • 목적
    • 후위 순회 출력
  • 필요 지식
    • 전위, 중위로 트리 모양 유추
      • 전위 순회와 후위 순회가 주어졌다
      • 전위 순회의 첫번째 인덱스 값은 a이다.
      • 중위 순회의 A번째 인덱스 값은 a이다.
      • 이때, 중위 순회의 1~A-1 인덱스의 값은 a의 왼쪽 자식이다.
      • 중의 순회의 A+1~N(마지막 인덱스) 인덱스의 값은 a의 오른쪽 자식이다.
  • 함수
    • printTree(int preIdx, int s, int e)
      • 후위 순회 출력 함수
      • 단계
        • 재귀적으로 루트 노드부터 왼쪽 자식→오른쪽 자식 순으로 탐색한다.
        • 맨 마지막으로 탐색된 노드부터 출력한다.
        • 출력 결과는 후위 순회와 같다.

 

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

public class Main {
    static int[] preList = new int[1001];
    static int[] inList = new int[1001];

    static int n;
    
    public static void printTree(int preIdx, int s, int e){
        if(s > e){
            return;
        }

        for(int i = 1; i<=n; i++){
            if(preList[preIdx] == inList[i]){
                printTree(preIdx+1, s,i-1);
                printTree(preIdx+(i-s+1), i+1, e);
                
                int curValue = preList[preIdx];
                System.out.print(curValue + " ");
                return;
            }
        }
        
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int T = Integer.parseInt(st.nextToken());
        for(int i = 1; i<=T; i++){
            Arrays.fill(preList, 0);
            Arrays.fill(inList, 0);
            
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j<=n; j++){
                preList[j] = Integer.parseInt(st.nextToken());
            }
            
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j<=n; j++){
                inList[j] = Integer.parseInt(st.nextToken());
            }
            
            printTree(1,1,n);
            System.out.println();
        }
    }
}

 

 

 

실패 방법

• 시도 방법
  • 전위, 중위 순회로 원래 트리 모양을 만듦
  • 트리 모양을 이용해서 후위 순회로 출력
• 실패 이유
  • 트리를 담는 자료구조가 배열이기 때문에 실패
  • 트리가 한 방향으로 쏠릴 시, 트리에 필요한 배열의 크기는 지수적으로 증가
  • 따라서 노드의 크기가 1000일 시, 메모리 초과가 일어남

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

public class Main {
    static int MAX = 1025;
    
    static int[] preList = new int[MAX];
    static int[] inList = new int[MAX];
    static int[] postList = new int[MAX];
    
    static int[] treeList = new int[MAX];
    
    static int n;
    
    public static void makeTree(int preIdx, int setIdx ,int s, int e){
        
        if(preIdx >= MAX || setIdx >= MAX){
            return;
        }

        if(s < 1 || e > n){
            return;
        }
        
        int targetIdx = 0;
        int targetValue = preList[preIdx];
        for(int i = s; i<=e; i++){
            if(preList[preIdx] == inList[i]){
                targetIdx = i;
                break;
            }
        }
        
        
        if(targetIdx == 0){
            return;
        }
        
        makeTree(preIdx+1,setIdx*2 , s, targetIdx-1);
        makeTree(preIdx+(targetIdx-s+1),setIdx*2+1 ,targetIdx+1, e);
        
        treeList[setIdx] = targetValue;
        return;
        
    }
    
    public static void printTree(){
        System.out.println("----------printTree----------");
        for(int i = 1; i<=10; i++){
            System.out.print(treeList[i] + " ");
        }
        System.out.println();
    }
    
    public static void printPost(int targetIdx){
        if(targetIdx >= MAX){
            return;
        }

        if(treeList[targetIdx] == 0){
            return;
        }

        printPost(targetIdx*2);
        printPost(targetIdx*2+1);
        System.out.print(treeList[targetIdx] + " ");
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int T = Integer.parseInt(st.nextToken());
        for(int i = 1; i<=T; i++){
            Arrays.fill(preList, 0);
            Arrays.fill(inList, 0);
            Arrays.fill(postList,0);
            Arrays.fill(treeList,0);
            
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j<=n; j++){
                preList[j] = Integer.parseInt(st.nextToken());
            }
            
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j<=n; j++){
                inList[j] = Integer.parseInt(st.nextToken());
            }
            
            makeTree(1,1,1,n);
            //printTree();
            printPost(1);
            System.out.println();
        }
    }
}