[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 길 찾기 게임 (Java)

[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 길 찾기 게임 : https://programmers.co.kr/learn/courses/30/lessons/42892

코딩테스트 연습 - 길 찾기 게임 | 프로그래머스

 

 

이번 문제는 딱히 알고리즘이랄 건 없고, 트리 자료구조를 구현할 수 있는지를 묻는 문제이다.

 

입력으로 nodeinfo를 받으면 각각의 정보를 Node로 변환하여 배열에 저장해준다.

그 후, 정렬을 해줘야 한다. 정렬을 하는 이유는 루트 노드부터 시작해서 순서대로 저장해주기 위해서다.

정렬은 y가 높고, x가 낮은 순서대로 한다. 예시의 정렬된 상태는 [7, 4, 2, 6, 1, 3, 9, 8, 5]가 된다.

정렬된 배열의 0번 인덱스가 트리의 root 노드가 된다.

 

정렬된 노드들을 트리에 하나씩 추가해준다.

Tree 클래스의 insert 함수를 만들어서 모든 노드들을 트리에 추가한다.

트리를 만들었다면 이제 preorder와 postorder를 찾아주면 된다.

preorder와 postorder는 학부 때 자료구조 수업에서 들은 게 생각나서 그 내용을 바탕으로 구현했다.

특별히 어려운 알고리즘은 없어서 코드를 보면 쉽게 이해할 수 있을 것이다.

 

 

총 걸린 시간 : 50분

난이도 : ★★☆☆☆

 

코드

class Solution {
    private int[] pre, post;
    private int idx = 0;

    public int[][] solution(int[][] nodeinfo) {
        int n = nodeinfo.length;
        pre = new int[n];
        post = new int[n];

        Node[] list = new Node[n];
        for (int i = 0; i < n; i++) {
            list[i] = new Node(nodeinfo[i][0], nodeinfo[i][1], i + 1);
        }
        Arrays.sort(list);

        Tree tree = new Tree(list[0]);
        for (int i = 1; i < n; i++) {
            tree.insert(list[i]);
        }

        preorder(tree.root);
        idx = 0;
        postorder(tree.root);

        return new int[][]{pre, post};
    }

    private void preorder(Node node) {
        if (node == null) return;

        pre[idx++] = node.value;
        preorder(node.left);
        preorder(node.right);
    }

    private void postorder(Node node) {
        if (node == null) return;

        postorder(node.left);
        postorder(node.right);
        post[idx++] = node.value;
    }
}

class Tree {
    Node root;

    Tree(Node root) {
        this.root = root;
    }

    public void insert(Node node) {
        Node thisNode = root;
        while (true) {
            if (node.x < thisNode.x) {
                if (thisNode.left != null) thisNode = thisNode.left;
                else {
                    thisNode.left = node;
                    break;
                }
            } else {
                if (thisNode.right != null) thisNode = thisNode.right;
                else {
                    thisNode.right = node;
                    break;
                }
            }
        }
    }
}

class Node implements Comparable<Node> {
    int x, y, value;
    Node left, right;

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

    @Override
    public int compareTo(Node other) {
        if (this.y == other.y) return this.x - other.x;
        else return other.y - this.y;
    }
}