97. 이진 탐색 트리 복원하기 (백준 18240)

 

문제

문제 링크 : https://www.acmicpc.net/problem/18240

18240번: 이진 탐색 트리 복원하기

문제

이진 트리란 각각의 노드가 0, 1, 2개의 자식 노드를 가지는 트리 자료 구조이다.

이진 탐색 트리란 각 노드의 왼쪽 서브트리(subtree)는 그 노드의 값보다 작은 노드 값들로, 오른쪽 서브트리(subtree)는 그 노드의 값보다 큰 노드 값들로 이루어져 있는 이진 트리를 말한다.

아래의 그림은 1부터 9까지의 수를 값으로 지닌 노드로 이루어져 있는 이진 탐색 트리의 예시이다.

또한, 이진 탐색 트리에 새로운 노드를 삽입하는 과정은 다음과 같다.

루트 노드부터 탐색하여 Insert 하는 값이 현재 노드의 값보다 크면 오른쪽 자식 노드를 방문, 작으면 왼쪽 자식 노드을 방문하는 것을 반복하다가 비어있는 자리에 해당하는 값을 가진 노드를 삽입한다.

아래는 값이 4인 노드를 루트로 하는 트리에 [2, 3, 5, 1]를 순차적으로 삽입하는 예시이다.

1부터 N까지의 모든 정수를 한 번씩 포함하고 있는 수열 A1, A2, ..., AN이 있다.

값이 A1인 노드를 루트로 하는 트리에 A2, A3, ..., AN 을 순서대로 삽입하려 한다.

N-1개의 노드를 삽입할 때마다 루트에서 그 노드에 도달하기 위해 거쳐야 하는 간선의 수, 즉 노드의 깊이가 주어질 때 A1, A2, ..., AN을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 길이 N이 주어진다. (2 ≤ N ≤ 300,000)

둘째 줄에는 A2부터 AN을 순서대로 삽입할 때마다 삽입된 노드의 깊이가 공백으로 구분하여 주어진다.

이때 노드의 깊이는 1이상 N미만의 자연수이다.

출력

가능한 수열이 있다면 첫째 줄에 수열 A1, A2, ..., AN의 값을 공백으로 구분하여 출력한다.

가능한 수열이 여러 개라면 아무거나 출력해도 좋다.

가능한 수열이 없다면 첫째 줄에 -1을 출력한다.

 

풀이

우선 트리의 최대 숫자 범위는 1~N일 것이다.

각각 숫자가 무엇인지 알기 위해서는 트리를 만들고 -> 중위순회로 탐색해서 몇번인지 알 수 있을 것이다.

그럼 입력받은 순서대로 트리만 만들어주면 된다.

노드가 순서대로가 아니기 때문에, 쉽게 만들기 위해서 트리의 깊이 별로 해당하는 노드를 저장하는 리스트도 만들었다.

각각의 깊이(차수)에 해당하는 노드를 입력받을 때마다, 그 부모차수의 개수를 고려하여 가능한 트리인지 아닌지 확인하고,

가능한 트리면 나눗셈을 통해 부모 차수에서 몇번째 노드인지 확인한 다음 알맞게 L,R로 자식을 연결하면 된다.

이때 노드를 만들때 입력받은 순서를 같이 저장해준다.

트리가 만들어지면 중위순회를 통해 각각의 값을 지정하고 -> 배열의 인덱스에 순서를 매칭시켜 값을 저장하면 된다.

 

코드

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

public class Main {

    static int T;
    //노드 수
    static int N;
    static ArrayList<Integer> depthList = new ArrayList<>();
    static int orderCount = 1;
    static int[] answer;

    static Node root;
    static int depthNum[];
    static HashMap<Integer,ArrayList<Node>> depthNode;

    static int order[];

    //루트를 뭐로 잡을까 -> 무조건 왼쪽부터 채운다고 생각.
    //각 숫자는 N개 가능.


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

            N = Integer.parseInt(br.readLine());
            answer = new int[N];

            st = new StringTokenizer(br.readLine());

            depthNode = new HashMap<>();
            depthNum = new int[N+1];

            root = makeNode(0, 0);
            depthNum[0]++;

            int depth;

            //i = num, cur = depth
            for(int i=0; i<N-1; i++) {    
                depth = Integer.parseInt(st.nextToken());
                depthNum[depth]++;

                //불가능
                if(depthNum[depth] > depthNum[depth-1]*2) {
                    System.out.println("-1");
                    return;
                }

                int parent = (depthNum[depth]-1)/2;    
                Node parentNode = depthNode.get(depth-1).get(parent);

                if(depthNum[depth]%2 == 1) {
                    parentNode.left = makeNode(i+1,depth);
                }else {
                    parentNode.right = makeNode(i+1,depth);
                }
            }

            inorder(root);
            //정답 출력
            for(int s : answer) {
                System.out.print(s+" ");
            }
    }

    public static Node makeNode(int num, int depth) {
        Node n = new Node(num);

        if(!depthNode.containsKey(depth)) {
            depthNode.put(depth, new ArrayList<Node>());
        }
        depthNode.get(depth).add(n);

        return n;
    }

    public static void inorder(Node node) {
        if(node != null) {
            if(node.left != null) inorder(node.left);            
            answer[node.num] = orderCount++;
            if(node.right != null) inorder(node.right);
        }
    }
}

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

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

결과

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!