#프로그래머스_길찾기 - Java 자바(2019 KAKAO BLIND RECRUITMENT)

#유형 : 트리, 자료구조

#난이도 : 프로그래머스 LEVEL 3

#입력을 우선순위큐를 사용하여 Y의 크기순, x는 작은순으로 정렬하면 된다. 우선순위큐를 사용해도 되고, 정렬기준을 통해 정렬을 해도 된다. 그러면 가장 앞에 루트노드가 올것이다. 그다음은 이진트리 조건에 따라 left, right를 정해서 트리를 완성하면 된다. 백준을 주로 풀어와서, 프로그래머스 문제는 좀 출력하기가 어색하다. 따라서 코드가 좀 복잡하게 보일 지라도, 기본 알고리즘은 간단하다

package programmers;
 
import java.util.ArrayList;
import java.util.PriorityQueue;
 
public class root {
    static No root;
    static ArrayList<Integer> re[];
    public static void main(String[] args) {
        int nodeinfo[][] = {{5,3},{11,5},{13,3},{3,5},{6,1},{1,3},{8,6},{7,2},{2,2}};
        int [][]answer = solution(nodeinfo);
        for(int i=0; i<2; i++) {
            for(int j=0; j<nodeinfo.length; j++)
                System.out.print(answer[i][j]+" " );
            System.out.println();
        }
    }
    public static int[][] solution(int[][] nodeinfo) {
        solve(nodeinfo);
        int[][] answer = new int[2][nodeinfo.length];
        for(int i=0; i<2; i++) {
                for(int j=0; j<nodeinfo.length; j++) {
                    answer[i][j] = re[i].get(j);
                }
        }
        return answer;
    }
    public static void solve(int[][] nodeinfo) {
//        int[][] answer = {};
        re = new ArrayList[2];
        for(int i=0; i<2; i++) {
                re[i]= new ArrayList<>();
        }
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for(int i=0; i<nodeinfo.length; i++) {
                pq.add(new Node(nodeinfo[i][0], nodeinfo[i][1], i+1));
        }
        
        Node tmp = pq.poll();
        No newNo = new No(tmp.num, tmp.x);
        root = newNo;
        
        while(!pq.isEmpty()) {
                Node nd = pq.poll();
                No n = new No(nd.num, nd.x);
                
                find(root, n);
        }
        preorder(root);
        postorder(root);
    }
    private static void find(No r, No n) {
        // TODO Auto-generated method stub
        if(r.x > n.x && r.left != null) {
            find(r.left, n);
        }else if(r.x > n.x && r.left == null) {
            r.left = n;
        }else if(r.x < n.x && r.right != null) {
            find(r.right, n);
        }else {
            r.right=n;
        }
        
    }
    
    public static void preorder(No n) {
        if(n == null) {
            return;
        }
//        System.out.println(n.num);
        re[0].add(n.num);
        preorder(n.left);
        preorder(n.right);
    }
    public static void postorder(No n) {
        if(n == null)
            return;
        postorder(n.left);
        postorder(n.right);
        re[1].add(n.num);
    }
    
    public static class No{
        int num;
        int x;
        No left;
        No right;
        public No(int n, int x) {
            this.num=n;
            this.x=x;
            this.left=null;
            this.right=null;
        }
    }
    public static class Node implements Comparable<Node>{
        int x;
        int y;
        int num;
        public Node(int x, int y, int num) {
            this.x=x;
            this.y=y;
            this.num=num;
        }
        @Override
        public int compareTo(Node o) {
            // TODO Auto-generated method stub
            if(this.y < o.y)
                return 1;
            else if(this.y == o.y) {
                if(this.x > o.x)
                    return 1;
                else
                    return -1;
            }
            return -1;
        }
    }
}