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

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

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

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

 

 문제 설명

입출력 예시

nodeinfo	result
[[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]]	[[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]]

이진트리의 노드를 좌표 평면에 그리고 간선(edge)를 모두 그리면 위와 같다. (이진트리의 각 노드에는 1부터 N까지 순서대로 번호가 붙어있다.)

전위 순회(preorder), 후위 순회(postorder)를 한 결과는 다음과 같고, 이것은 각 팀이 방문해야 할 순서를 의미한다.

• 전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3
• 후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7

이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때, 노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return 하도록 solution 함수를 완성하자.

 문제 해결 방법

BST코드 응용하여 풀이하였습니다.

1. Node 추가
   • key, x, y, leftChild, rightChild 추가
   • compareTo로 root값부터 넣기 위해 높이 y가 가장 높은 순으로 정렬 (높이가 같을 경우 x가 작은 것 순서로 정렬)
2. BST addNode 추가
   • root가 없을 경우, root에 추가하고 parentNode보다 x값이 작으면 왼쪽, 크면 오른쪽에 노드를 추가함
3. preOrder, postOrder 메서드 추가
   • 전위 순회, 후위 순회 메서드를 추가하여 List answer에 값을 저장하도록 함
4. answer 가져오기
   • getAnswer메서드를 통해 preOrder, postOrder 메서드를 통해 얻어온 answer값을 answer[][] array에 넣어서 반환

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    Node root;

    public int[][] solution(int[][] nodeinfo) {
        List<Node> nodeList = new ArrayList<>();
        for (int i = 0; i < nodeinfo.length; i++) {
            nodeList.add(new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]));
        }
        Collections.sort(nodeList);

        for (int i = 0; i < nodeList.size(); i++) {
            addNode(nodeList.get(i));
        }

        return getAnswer();
    }

    private void addNode(Node node) {
        if (root == null) {
            root = node;
        } else {
            Node parentNode, focusNode = root;
            while (focusNode != null) {
                parentNode = focusNode;
                if (node.x < parentNode.x) {
                    focusNode = parentNode.leftChildNode;
                    if (focusNode == null) {
                        parentNode.leftChildNode = node;
                        return;
                    }
                } else {
                    focusNode = parentNode.rightChildNode;
                    if (focusNode == null) {
                        parentNode.rightChildNode = node;
                        return;
                    }
                }
            }
        }
    }
    private int[][] getAnswer() {
        List<Integer> preOrderAnswer = new ArrayList<>();
        List<Integer> postOrderAnswer = new ArrayList<>();

        preOrderTraverse(root, preOrderAnswer);
        postOrderTraverse(root, postOrderAnswer);

        int[][] answer = new int[2][preOrderAnswer.size()];
        answer[0] = preOrderAnswer.stream().mapToInt(i -> i).toArray();
        answer[1] = postOrderAnswer.stream().mapToInt(i -> i).toArray();
        return answer;
    }

    private void postOrderTraverse(Node node, List<Integer> answer) {
        if (node != null) {
            postOrderTraverse(node.leftChildNode, answer);
            postOrderTraverse(node.rightChildNode, answer);
            answer.add(node.key);
        }
    }

    private void preOrderTraverse(Node node, List<Integer> answer) {
        if (node != null) {
            answer.add(node.key);
            preOrderTraverse(node.leftChildNode, answer);
            preOrderTraverse(node.rightChildNode, answer);
        }
    }
}

class Node implements Comparable<Node> {
    int key;
    int x;
    int y;
    Node leftChildNode;
    Node rightChildNode;

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

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