카카오 코딩테스트 - 길 찾기 게임

https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

2019 카카오 신입 공채 1차 코딩 테스트 문제 해설

문제 자체는 이해하는데 그렇게 어렵지 않다. 각각의 node의 좌표(x,y)가 배열로 주어지고, 이 노드들로 트리를 만들어서 전위/후위 순회하는 문제이다.

 

실제로 문제를 풀면서도, 각 노드들로 어떻게 트리를 만들지에 대해 많이 생각했던 것 같다. 처음 코드를 작성하고, 여러 케이스를 돌렸을 때 다 통과했는데 결과적으로 제출했을 때는 틀렸다고 나왔서 풀이법은 보았다.

 

문제 해결은 다음과 같다,

1. 좌표,번호,왼쪽/오른쪽 노드를 속성으로 가지는 Node 정보를 저장하는 클래스를 만든다.

2. 입력에 따라 Node 객체를 만들고 list에 저장한다. y가 큰 값을 기준으로 정렬, 만약 y가 같다면 x가 작은 값으로 정렬한다.

3. root노드를 기준으로 Node를 하나씩 추가한다(재귀함수를 사용)

4. 전위/후위 순회를 한다.

 

전체 아이디어는 간단한데, 어떻게 코드로 옮길지가 문제이다.

먼저 2번 과정을 진행한 이유는 list에서 Node를 빼올 때, 이진트리의 조건에 맞게 빼오기 위함이다.

3번 과정은, root Node를 기준으로 root.left가 null이면 Node를 넣고, null이 아니면 다시 root.left를 기준으로 재귀를 돈다.

문제에서 parent node는 child node보다 y값이 크고, child node의 x값이 parent node보다 작으면 왼쪽, 크면 오른쪽에 두게 된다. 이 조건을 재귀함수에 추가해준다.

 

// https://www.welcomekakao.com/learn/courses/30/lessons/42888?language=java
// 길 찾기 게임

import java.util.*;

class Solution {

    static int index = 0;

    public int[][] solution(int[][] nodeinfo) {

        List<Node> list = new ArrayList<Node>();

        for (int a = 0; a < nodeinfo.length; a++) {
            list.add(new Node(nodeinfo[a][0], nodeinfo[a][1], a + 1));
        }

        Collections.sort(list, new Comparator<Node>() { // 노드들을 y가 높은 순으로 정렬, y가 같다면 x가 낮은 순으로 정렬
            public int compare(Node n1, Node n2) {
                if (n1.y > n2.y) {
                    return -1;
                } else if (n1.y < n2.y) {
                    return 1;
                } else {
                    if (n1.x > n2.x) {
                        return 1;
                    } else if (n1.x < n2.x) {
                        return -1;
                    } else {
                        return 0;
                    }
                }
            }
        });

        Node root = list.get(0);
        int[][] answer = new int[2][list.size()];

        for (int i = 1; i < list.size(); i++) {
            addNode(root, list.get(i));
        }

        preorder(answer, root);
        index = 0;
        postorder(answer, root);

        return answer;
    }

    void addNode(Node parent, Node child) {
        if (parent.x > child.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[][] arr, Node root) { // 전위순회

        if (root != null) {
            arr[0][index++] = root.num;
            preorder(arr, root.left);
            preorder(arr, root.right);
        }
    }

    void postorder(int[][] arr, Node root) { // 후위순회
        if (root != null) {
            postorder(arr, root.left);
            postorder(arr, root.right);
            arr[1][index++] = root.num;
        }
    }
}

class Node {
    int x;
    int y;
    int num;
    Node left;
    Node right;

    Node(int x, int y, int num) {
        this.x = x;
        this.y = y;
        this.num = num;
    }
}

 

문제 해설에도 나왔지만 이 문제의 핵심은 어떻게 트리모양으로 만들지에 대한 것인데, 이 부분을 너무 어렵게 생각했던 것 같다. 

그래서 혼자 풀 때, 시간을 많이 잡아먹었는데 생각해보면 재귀로 간단하게 풀 수 있는 문제였다.