Lv3. 길찾기 게임

 

https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=2%2C3%2C4&languages=java&page=7

코딩테스트 연습 | 프로그래머스 스쿨

 

 

 

주어진 노드 좌표 정보를 이용해 이진 트리를 구성하고,
전위 순회와 후위 순회를 통해 결과를 반환하는 문제다.

 

먼저 노드 정보를 객체로 변환하고,

y값을 기준으로 내림차순, x값을 기준으로 오름차순으로 정렬한다.

 

이 정렬된 순서대로 첫 번째 노드를 루트로 설정하고 나머지 노드를 트리에 삽입한다.

트리 삽입은 현재 노드와 x값을 비교하여 왼쪽 또는 오른쪽 자식 노드에

배치하는 방식으로 이루어진다.

트리 구성이 끝난 후, 전위 순회와 후위 순회를 수행하며 각각의 결과를 기록한다.
전위 순회는 루트 → 왼쪽 → 오른쪽, 후위 순회는 왼쪽 → 오른쪽 → 루트 순으로 탐색하며,
결과는 2차원 배열에 저장된다.

이를 통해 정렬된 트리에서 전위 순회와 후위 순회 결과를

반환하는 것이 최종 목표다.

 

 

import java.util.*;

class Solution {
    int[][] result;
    int idx;
    
    public int[][] solution(int[][] nodeinfo) {
        int size = nodeinfo.length;
        Node[] nodes = new Node[size];
        for(int i = 0 ; i < size ; i++){
            nodes[i] = new Node(nodeinfo[i][0],nodeinfo[i][1],i+1,null,null);
        }
        Arrays.sort(nodes, (n1, n2) -> (n1.y == n2.y) ? n1.x - n2.x : n2.y - n1.y);
        
        Node root = nodes[0];
        for(int i = 1; i < size ; i++){
            insertNode(root, nodes[i]);
        }
        
        result = new int[2][size];
        
        idx = 0;
        preorder(root);
        idx = 0;
        postorder(root);
        return result;       
    }
    public void insertNode(Node parent, Node child) {
        if(parent.x > child.x) {
            if(parent.left == null) parent.left = child;
            else insertNode(parent.left, child);
        } else {
            if(parent.right == null) parent.right = child;
            else insertNode(parent.right, child);
        }
    }
        public void preorder(Node root) {
        if(root != null) {
            result[0][idx++] = root.value;
            preorder(root.left);
            preorder(root.right);
        }
    }
    
    public void postorder(Node root) {
        if(root != null) {
            postorder(root.left);
            postorder(root.right);
            result[1][idx++] = root.value;
        }
    }
    
    class Node{
        int x;
        int y;
        int value;
        Node left;
        Node right;
        
        public Node(int x, int y, int value, Node left, Node right){
            this.x = x;
            this.y = y;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}