프로그래머스 Lv.3) 길 찾기 게임

2019 KAKAO BLIND RECRUITMENT

길 찾기 게임

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

풀이

 

우선 순위 큐를 통해 Node의 순서를 정해주려 했다. 하지만, compareTo 메소드를 잘못 설정해서인지, 아니면 우선순위큐가 지닌 unstable한 정렬 때문인지 제대로 순차 저장이 되지 않았다. 그래서 다른 분들은 어떻게 해결했는지 찾아보았다.

 

배열에 대해 Arrays의 sort를 이용하며, Comparator를 통해 정렬하는 방법으로 푼 글을 보았다. 그래서 바로 배열로 만들기로 결정하고 Node 저장 및 정렬을 해주었다.

 

다음에 저장된 배열을 Node의 관계에 따라, root부터 붙여주면서 edge가 연결된 Node를 만들었다.

 

그 다음은 전위 순회, 후위 순회를 메소드의 재귀 호출을 통해 답을 직접 찾아주었다.

전위 순회는 Root -> left -> right 순서기 때문에, 메소드에 들어오자마자 node의 number를 저장해주고 left와 right를 다시 파라메터로 넘겨 진행했다.

후위 순회는 left->right->root 순서기 때문에, left와 right를 파라메터로 넘겨 재귀를 진행하면서, 메소드 종료 직전에 답을 저장했다.

 

문제는 쉬운 문제였지만, 생각보다 고전한 것 같다.

 

 

기억에 남길 것 : Arrays.sort에 직접 Comparator를 만들 때는, compare 메소드이다. <-----> Comparable ~> compareTo

 

코드

 

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    int ansIdx;
    int[][] answer;
    public int[][] solution(int[][] nodeinfo) {
        answer = new int[2][nodeinfo.length];
        Node[] nodes = inItNodes(nodeinfo); // 입력받은 node 정보 저장
        
        Node root = nodes[0];
        for(int i=1; i<nodes.length; i++) { // Node 이어주기
            makeNode(root, nodes[i]);
        }
        ansIdx =0;  // 답 배열의 idx 초기화
        findPreorder(root);     // 전위 순회
        ansIdx =0;  // 답 배열의 idx 초기화
        findPostorder(root);    // 후위 순회
        
        return answer;
    }
    
    private Node[] inItNodes(int[][] nodeinfo) {
        Node[] nodes = new Node[nodeinfo.length];
        for(int i=0; i<nodeinfo.length; i++) {
            nodes[i] = new Node((i+1), nodeinfo[i][0], nodeinfo[i][1]);
        }
        // sorting
        Arrays.sort(nodes, new Comparator<Node>() {
            public int compare(Node n1, Node n2) {
                return n2.y == n1.y ? n1.x-n2.x : n2.y -n1.y;
            }
        });
        return nodes;
    }
    
    private void makeNode(Node root, Node child) {
        if(root.x > child.x) {
            if(root.left != null) {
                makeNode(root.left, child);
            } else {
                root.left = child;
            }
        } else {
            if(root.right != null) {
                makeNode(root.right, child);
            } else {
                root.right = child;
            }
        }
    }
    private void findPreorder(Node root) {
        answer[0][ansIdx++] = root.idx;
        if(root.left != null) {
            findPreorder(root.left);
        }
        if(root.right != null) {
            findPreorder(root.right);
        }
    }
    
    private void findPostorder(Node root) {
        if(root.left != null) {
            findPostorder(root.left);
        }
        if(root.right != null) {
            findPostorder(root.right);
        }
        answer[1][ansIdx++] = root.idx;
        
    }
}

class Node {
    int idx;
    int x;
    int y;
    Node left;
    Node right;
    
    public Node(int idx, int x, int y) {
        this.idx = idx;
        this.x = x;
        this.y = y;
    }
}