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

🖇️ 문제 링크

코딩테스트 연습 - 길 찾기 게임

전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다. 내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다. 라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다.

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

 

---

📝 문제 분석

node를 y값 내림차순, x값 오름차순으로 정렬

첫번 째 원소를 root로 트리를 이진 트리를 만들자

node = idx, left, right, 각 단계에서 x 비교

이진 트리 다 만들었으면 전위 순회, 후위 순회 수행

 

---

⌨️ 코드

import java.util.*;

class Solution {
    int cnt = 0;
    
    public int[][] solution(int[][] nodeinfo) {
        int n = nodeinfo.length;
        Node[] nodeArr = new Node[n];
       	for(int i = 0; i < n; i++)
        	nodeArr[i] = new Node(i + 1, nodeinfo[i][1], nodeinfo[i][0]); 
        
        // y값 내림차순, x값 오름차순으로 정렬
       	Arrays.sort(nodeArr, (n1, n2) -> {
            if(n1.y != n2.y) return n2.y - n1.y;
            return n1.x - n2.x;
        });
        
        // 이진 트리를 만들자, 첫번 째가 루트
        Node root = nodeArr[0];
        for(int i = 1; i < n; i++)
            root.addNode(nodeArr[i]);
        
        int[][] ans = new int[2][n];
        //전위 순회
        root.preOrder(ans, 0);
        cnt = 0;
        //후위 순회
        root.postOrder(ans, 1);
        
        return ans;
    }
    
    class Node {
        int idx, y, x;
        Node left, right;
        
        Node(int idx, int y, int x) {
            this.idx = idx;
            this.y = y;
            this.x = x;
        }
        
        void addNode(Node n) {
            if(this.x < n.x) {
                if(this.right == null)
                    this.right = n;
                else
                    this.right.addNode(n);
            } else {
                if(this.left == null)
                    this.left = n;
                else
                    this.left.addNode(n);
            }
        }
        
        void preOrder(int[][] ans, int type) {
            ans[type][cnt++] = this.idx;
            if(this.left != null)
                this.left.preOrder(ans, type);
            if(this.right != null)
                this.right.preOrder(ans, type);
        }
        
        void postOrder(int[][] ans, int type) {
            if(this.left != null)
                this.left.postOrder(ans, type);
            if(this.right != null)
                this.right.postOrder(ans, type);
           	ans[type][cnt++] = this.idx; 
        }
    }
}

 

Uploaded by Notion2Tistory v1.1.0