[프로그래머스] 42892 길 찾기 게임 - JAVA

[프로그래머스] 42892 길 찾기 게임 - JAVA 

문제

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

 

문제 분석

조건

• 각 노드는 (x, y) 좌표로 주어짐
• y좌표가 클수록 루트에 가까움
• x좌표를 기준으로 왼쪽/오른쪽 자식이 결정됨
• 전위 순회, 후위 순회를 한 결과를 배열로 반환해야 함

풀이방법

• 노드를 y좌표 기준 내림차순 정렬하면 루트부터 정렬된다. y가 같다면 x 오름차순으로 정렬
• 가장 위에 있는 노드를 루트로 설정
• 나머지 노드들을 이진 트리 규칙(x좌표 기준)에 따라 루트에 삽입
  • 왼쪽이면 x < 부모.x, 오른쪽이면 x > 부모.x
• 전위 순회(preorder)와 후위 순회(postorder)를 각각 수행하여 결과 저장

코드

import java.util.*;

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

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

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

class Solution {
    static int[][] answer;
    static int answerIndex;

    public int[][] solution(int[][] nodeinfo) {
        answer = new int[2][nodeinfo.length];
        PriorityQueue<Node> pq = new PriorityQueue<>();

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

        Node root = pq.poll();
        while (!pq.isEmpty()) {
            insert(root, pq.poll());
        }

        answerIndex = 0;
        preorder(root);

        answerIndex = 0;
        postorder(root);

        return answer;
    }

    private void insert(Node parent, Node child) {
        if (child.x < parent.x) {
            if (parent.left == null) parent.left = child;
            else insert(parent.left, child);
        } else {
            if (parent.right == null) parent.right = child;
            else insert(parent.right, child);
        }
    }

    private void preorder(Node node) {
        answer[0][answerIndex++] = node.num;
        if (node.left != null) preorder(node.left);
        if (node.right != null) preorder(node.right);
    }

    private void postorder(Node node) {
        if (node.left != null) postorder(node.left);
        if (node.right != null) postorder(node.right);
        answer[1][answerIndex++] = node.num;
    }
}

시간복잡도

 

• 정렬: O(N log N)
• 트리 구성: O(N log N) (이진 삽입)
• 순회: O(N)