2019 KAKAO BLIND RECRUITMENT : 길 찾기 게임

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

코딩테스트 연습 - 길 찾기 게임

// 코드

import java.util.*;
 
class Solution {
    
    class Node {
        
        int id;
        int x, y;
        Node left;
        Node right;
        
        Node(int id, int x, int y) {
            this.id = id;
            this.x = x;
            this.y = y;
        }        
    };
    
    int idx = 0;
    List<Node> Nodes = new ArrayList<Node>();    
    // y가 큰 순서대로 y가 같으면 x가 작은 순서대로 정렬이된다.
    Comparator<Node> Comp = new Comparator<Node>() {
        public int compare(Node a, Node b) {
            if(a.y == b.y) {
                return a.x - b.x;
            }
            return b.y - a.y;
        }
    }; 
    
    // 트리노드를 추가한다.
    void addNode(Node parent, Node child) {
        if(child.x < parent.x) { // 왼쪽 자식노드 추가
            if(parent.left == null) parent.left = child;
            else addNode(parent.left, child);
        } else { // 오른쪽 자식노드 추가
            if(parent.right == null) parent.right = child;
            else addNode(parent.right, child);
        }
    }
    
    // 전위순회
    void preOrder(int[][] answer, Node node) {
        if(node == null) return;
        
        answer[0][idx++] = node.id;
        preOrder(answer, node.left);
        preOrder(answer, node.right);        
    } 
    
    // 후위순회    
    void postOrder(int[][] answer, Node node) {
        if(node == null) return;
                
        postOrder(answer, node.left);
        postOrder(answer, node.right);
        answer[1][idx++] = node.id;
    }
    
    // main
    public int[][] solution(int[][] nodeinfo) {
        
        // 노드들을 생성한다.
        int size = nodeinfo.length;
        for(int i=0; i<size; i++) {
            Nodes.add(new Node(i+1, nodeinfo[i][0], nodeinfo[i][1]));
        }
        
        // y가 큰 순서대로 y가 같으면 x가 작은 순서대로 정렬
        Nodes.sort(Comp);
        
        // 이진트리를 완성한다.
        Node root = Nodes.get(0);
        for(int i=1; i<size; i++) {            
            addNode(root, Nodes.get(i));
        }
        
        // 전위/후위 순회 
        int[][] answer = new int[2][size];
        preOrder(answer, root);
        idx = 0;
        postOrder(answer, root);
        
        return answer;
    }
}

// 복습

import java.util.*;
 
class Solution {
    
    class Node {
        int id;
        int x, y;
        Node left;
        Node right;
        
        Node(int id, int x, int y) {
            this.id = id;
            this.x = x;
            this.y = y;            
        }        
    }
    
    List<Node> Nodes = new ArrayList<>();
    Comparator<Node> Comp = new Comparator<>() {
        public int compare(Node a, Node b) {
            if(a.y == b.y) return a.x - b.x;
            return b.y - a.y;
        }
    };
    int idx = 0;
    
    // 트리노드를 추가한다.
    void addNode(Node parent, Node child) {
        // 왼쪽 자식노드에 추가
        if(child.x < parent.x) {
            if(parent.left == null) parent.left = child;
            else addNode(parent.left, child);
        }
        // 오른쪽 자식노드에 추가
        else {
            if(parent.right == null) parent.right = child;
            else addNode(parent.right, child);
        }
    }
    
    // 전위순회
    void preOrder(int[][] answer, Node node) {
        if(node == null) return;
        
        answer[0][idx++] = node.id;
        preOrder(answer, node.left);
        preOrder(answer, node.right);
    }
    
    // 후위순회
    void postOrder(int[][] answer, Node node) {
        if(node == null) return;
                
        postOrder(answer, node.left);
        postOrder(answer, node.right);
        answer[1][idx++] = node.id;
    }
    
    public int[][] solution(int[][] nodeinfo) {
        
        // 노드들을 생성한다.
        int size = nodeinfo.length;
        for(int i=0; i<size; i++) {
            Nodes.add(new Node(i+1, nodeinfo[i][0], nodeinfo[i][1]));
        }
        
        // y가 큰 순서대로, y가 같다면 x가 작은 순서대로 정렬한다.
        Nodes.sort(Comp);
        
        // 이진트리를 완성한다.
        Node root = Nodes.get(0); // root
        for(int i=1; i<size; i++) {
            addNode(root, Nodes.get(i));
        }
        
        // 전위, 후위 순회
        int[][] answer = new int[2][size];
        preOrder(answer, root);
        idx = 0;
        postOrder(answer, root);
        
        return answer;
    }
}