프로그래머스 2019 KAKAO BLIND RECRUITMENT - 길 찾기 게임[JAVA]

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42892

프로그래머스

코드:

 

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

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

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

class Solution {

    int[] parents;
    int[] left;
    int[] right;
    int rootNode;
    List<Integer> preorderResult = new ArrayList<>();
    List<Integer> postorderResult = new ArrayList<>();

    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = new int[2][nodeinfo.length];
        parents = new int[nodeinfo.length + 1];
        left = new int[nodeinfo.length + 1];
        right = new int[nodeinfo.length + 1];
        List<Node> nodeList = new ArrayList<>(nodeinfo.length + 1); // x 오른차순으로 정렬
        for (int i = 0; i < nodeinfo.length; i++) {
            nodeList.add(new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]));
        }
        nodeList.sort(Comparator.comparingInt(o -> o.x));
        makeTree(nodeList, -1, 0);
        preorder(rootNode);
        postorder(rootNode);
        for (int i = 0; i < nodeinfo.length; i++) {
            answer[0][i] = preorderResult.get(i);
            answer[1][i] = postorderResult.get(i);
        }
        return answer;
    }

    public void preorder(int parentNode) {
        preorderResult.add(parentNode);
        if(left[parentNode] > 0) preorder(left[parentNode]);
        if(right[parentNode] > 0) preorder(right[parentNode]);
    }

    public void postorder(int parentNode) {
        if(left[parentNode] > 0) postorder(left[parentNode]);
        if(right[parentNode] > 0) postorder(right[parentNode]);
        postorderResult.add(parentNode);

    }

    //child: 1:left 2:right
    public void makeTree(List<Node> nodeList, int parent, int child) {
        if(nodeList.size() < 1) return;
        //1. 루트 찾기
        int root = 0;
        int idx = 0;
        int pLevel = Integer.MIN_VALUE;
        for (int i = 0; i < nodeList.size(); i++) {
            if(pLevel < nodeList.get(i).y){
                idx = i;
                root = nodeList.get(i).idx;
                pLevel = nodeList.get(i).y;
            }
        }
        //2. 정보 저장
        if(parent == -1){
            rootNode = root;
        }
        parents[root] = parent;

        if(child == 1){
            left[parent] = root;
        } else if (child == 2) {
            right[parent] = root;
        }
        //3. dfs
        makeTree(nodeList.subList(0, idx), root, 1);
        makeTree(nodeList.subList(idx + 1, nodeList.size()), root, 2);

    }
}

public class Main {

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] nodeinfo = {
                {5,3},
                {11,5},
                {13,3},
                {3,5},
                {6,1},
                {1,3},
                {8,6},
                {7,2},
                {2,2}
        };
        sol.solution(nodeinfo);
    }
}