프로그래머스 Lv3 길 찾기 게임 Java

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42892

구현방법

• y좌표 기준 내림차순 정렬, y좌표가 동일하면 x좌표 기준 오름차순 정렬
• 제일 큰 y좌표를 가진 노드를 루트노드로 설정 후 이진트리 구성
• 전위순회, 후위순회 결과 출력

코드

import java.util.*;
class Solution {
    class Node implements Comparable<Node>{
        int num;
        int x,y;
        Node left,right;
        public Node(int num, int x, int y){
            this.num = num;
            this.x = x;
            this.y = y;
        }
        @Override
        public int compareTo(Node n){
            if(this.y<n.y){
                return 1;
            }
            else if(this.y>n.y){
                return -1;
            }
            else{
                if(this.x>n.x){
                    return 1;
                }
                else if(this.x<n.x){
                    return -1;
                }
                else
                    return 0;
            }
        }
    }
    static int answer[][];
    static int index = 0;
    public int[][] solution(int[][] nodeinfo) {
        answer= new int[2][nodeinfo.length];
        List<Node> list = new ArrayList<>();
        for(int i=0;i<nodeinfo.length;i++){
            list.add(new Node(i+1,nodeinfo[i][0],nodeinfo[i][1]));
        }
        Collections.sort(list);
        Node root = list.get(0);
        for(int i=1;i<list.size();i++){
            connect(root,list.get(i));
        }
        preOrder(root);
        index=0;
        postOrder(root);
        return answer;
    }
    public void connect(Node parent, Node child){
        if(parent.x>child.x){
            if(parent.left==null){
                parent.left = child;
            }
            else{
                connect(parent.left,child);
            }
        }
        else{
            if(parent.right ==null){
                parent.right = child;
            }
            else{
                connect(parent.right,child);
            }
        }
    }
    public void preOrder(Node root){
        if(root!=null){
            answer[0][index++] = root.num;
            if(root.left!=null) preOrder(root.left);
            if(root.right!=null) preOrder(root.right);
        }
    }
    public void postOrder(Node root){
        if(root!=null){
            if(root.left!=null) postOrder(root.left);
            if(root.right!=null) postOrder(root.right);
            answer[1][index++] = root.num;
        }
    }
}