[Lv.3] 길찾기 게임 : Java

프로그래머스

 

import java.util.*;

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

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

        // 1) 노드 묶음: (x, y, index)
        List<Node> nodes = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            nodes.add(new Node(nodeinfo[i][0], nodeinfo[i][1], i + 1)); // 인덱스는 1부터
        }

        // 2) y 내림차순, x 오름차순 정렬
        nodes.sort((a, b) -> {
            if (a.y != b.y) return b.y - a.y; // y desc
            return a.x - b.x;                 // x asc
        });

        // 3) 첫 노드를 루트로, 나머지는 x 기준으로 BST 삽입
        Node root = nodes.get(0);
        for (int i = 1; i < n; i++) insert(root, nodes.get(i));

        // 4) 전위/후위 순회
        int[] pre = new int[n];
        int[] post = new int[n];
        int[] pi = new int[1];   // 전위 인덱스 포인터
        int[] poi = new int[1];  // 후위 인덱스 포인터

        preorder(root, pre, pi);
        postorder(root, post, poi);

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

    // x 좌표 기준으로 왼/오 삽입
    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, int[] out, int[] idx) {
        if (node == null) return;
        out[idx[0]++] = node.idx;          // 루트
        preorder(node.left, out, idx);     // 왼
        preorder(node.right, out, idx);    // 오
    }

    private void postorder(Node node, int[] out, int[] idx) {
        if (node == null) return;
        postorder(node.left, out, idx);    // 왼
        postorder(node.right, out, idx);   // 오
        out[idx[0]++] = node.idx;          // 루트
    }
}