[프로그래머스] level3 길 찾기 게임 (Java)

문제 링크

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

문제 설명

이 문제는 2차원 평면상에 노드들이 주어지고, 이를 이용해 이진 트리(Binary Tree) 를 구성한 뒤, 전위 순회(Preorder Traversal) 와 후위 순회(Postorder Traversal) 결과를 구하는 문제입니다.

• 규칙

1. 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
2. 모든 노드는 서로 다른 x값을 가진다.
3. 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
4. 자식 노드의 y 값은 항상 부모 노드보다 작다.
5. 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
6. 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

아이디어

• 트리 구성
  y 값을 기준으로 내림차순 정렬하면, 가장 큰 y 값을 가진 노드가 루트가 됩니다.
  x 값을 비교하면서 왼쪽(x가 작은 값)과 오른쪽(x가 큰 값)으로 자식 노드를 배치합니다.
  이를 통해 이진 탐색 트리(Binary Search Tree, BST) 를 구성합니다.

• 전위 순회(Preorder Traversal)
  순회 순서: 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
  루트 노드를 방문한 후, 왼쪽 서브트리를 방문하고, 마지막으로 오른쪽 서브트리를 방문합니다.

• 후위 순회(Postorder Traversal)
  순회 순서: 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
  왼쪽 서브트리를 먼저 방문하고, 오른쪽 서브트리를 방문한 후, 루트 노드를 방문합니다.

구현

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

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

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

class Tree {
    Node root;

    public void add(Node node) {
        if (root == null) {
            root = node;
            return;
        }

        Node tmp = root;
        while (true) {
            if (node.x > tmp.x) {
                if (tmp.right == null) {
                    tmp.right = node;
                    break;
                }
                tmp = tmp.right;
            }
            if (node.x < tmp.x) {
                if (tmp.left == null) {
                    tmp.left = node;
                    break;
                }
                tmp = tmp.left;
            }
        }
    }

    public void preorderAndSave(List<Integer> result, Node root) {
        if (root == null) {
            return;
        }

        result.add(root.idx);
        preorderAndSave(result, root.left);
        preorderAndSave(result, root.right);
    }

    public void postorderAndSave(List<Integer> result, Node root) {
        if (root == null) {
            return;
        }

        postorderAndSave(result, root.left);
        postorderAndSave(result, root.right);
        result.add(root.idx);
    }
}

class Solution {
    public int[][] solution(int[][] nodeinfo) {
        List<Node> list = new ArrayList<>();
        for (int i = 0; i < nodeinfo.length; i++) {
            int idx = i + 1;
            int x = nodeinfo[i][0];
            int y = nodeinfo[i][1];
            list.add(new Node(idx, x, y));
        }
        Collections.sort(list, (o1, o2) -> {
            if (o2.y == o1.y) {
                return o1.x - o2.x;
            }
            return o2.y - o1.y;
        });

        Tree tree = new Tree();
        for (Node node : list) {
            tree.add(node);
        }

        List<Integer> preorderResultList = new ArrayList<>();
        tree.preorderAndSave(preorderResultList, tree.root);

        List<Integer> postorderResultList = new ArrayList<>();
        tree.postorderAndSave(postorderResultList, tree.root);

        int[] preorderResultArray = preorderResultList.stream()
                .mapToInt(i -> i)
                .toArray();
        int[] postorderResultArray = postorderResultList.stream()
                .mapToInt(i -> i)
                .toArray();

        return new int[][]{preorderResultArray, postorderResultArray};
    }
}

시간 복잡도

• 노드 리스트 생성: O(N)
• 노드 정렬: O(N log N)
• 이진 탐색 트리 생성: O(N log N)
• 전위 순회: O(N)
• 후위 순회: O(N)

전체 시간 복잡도: O(N log N) + O(N) ≈ O(N log N)