[BaekJoon] 12767 Ceiling Function (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static int prototypeNum;
    static int layerNum;
    static Set<String> prototypes; // ceiling prototype 정보들, 중복 방지를 위해 Set 이용

    static void input() {
        Reader scanner = new Reader();

        prototypeNum = scanner.nextInt();
        layerNum = scanner.nextInt();
        prototypes = new HashSet<>();

        for(int idx = 0; idx < prototypeNum; idx++) {
            Tree tree = new Tree(); // 각 ceiling prototype에 대한 BST 생성
            // BST에 값 추가
            for(int nodeNum = 0; nodeNum < layerNum; nodeNum++) {
                tree.insert(scanner.nextInt());
            }
            // prototypes에 현재 ceiling prototype 정보 추가
            addNewTreeShape(tree);
        }
    }

    static void addNewTreeShape(Tree tree) {
        Collections.sort(tree.nodeNums); // 각 layer의 노드 번호를 오름차순으로 정렬
        StringBuilder sb = new StringBuilder();

        // 각 layer의 노드 번호를 이어서 문자열로 만든다
        for(int nodeNum : tree.nodeNums) {
            sb.append(nodeNum);
        }

        // 현재 ceiling prototype 정보를 prototypes에 추가
        prototypes.add(sb.toString());
    }

    static class Node { // 트리의 각 노드를 나타내는 클래스
        int value; // 현재 노드의 값
        Node left; // 현재 노드의 왼쪽 노드
        Node right; // 현재 노드의 오른쪽 노드

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    static class Tree { // prototype에 해당하는 BST를 나타내는 클래스
        Node root; // 루트 노드
        List<Integer> nodeNums; // prototype에 있는 노드들의 노드 번호를 담는 리스트

        public Tree() {
            this.nodeNums = new ArrayList<>();
        }

        public void insert(int value) {
            Node newNode = new Node(value); // 추가하고자 하는 값으로 노드 하나 생성
            int nodeNum = 1; // 루트 노드의 노드 번호가 1이기 때문에 초기값을 1로 설정

            if(root == null) { // 만약 아직 루트 노드가 없다면
                // 새롭게 만든 노드를 루트 노드로 설정하고 nodeNums에 노드 번호 추가
                root = newNode;
                nodeNums.add(nodeNum);
                return;
            }

            Node cur = root;
            Node prev = null;
            // 루트 노드가 있다면 현재 추가하고자 하는 노드가 추가되어야 할 위치를 찾고 그 위치에 노드를 추가한다
            // 노드를 추가할 때, 해당 노드 번호를 nodeNums에 추가한다
            // 노드 번호는 아래와 같이 구한다
            //  - 부모 노드에서 왼쪽에 해당하는 노드는 부모 노드 번호 * 2
            //  - 부모 노드에서 오른쪽에 해당하는 노드는 부모 노드 번호 * 2 + 1
            while(cur != null) {
                prev = cur;

                if(cur.value > value) {
                    cur = cur.left;
                    nodeNum *= 2;
                    if(cur == null) {
                        prev.left = newNode;
                        nodeNums.add(nodeNum);
                        return;
                    }
                } else {
                    cur = cur.right;
                    nodeNum = nodeNum * 2 + 1;
                    if(cur == null) {
                        prev.right = newNode;
                        nodeNums.add(nodeNum);
                        return;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        input();
        System.out.println(prototypes.size());
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}