[JAVA] 프로그래머스 LEVEL3 길 찾기 게임

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

프로그래머스

코딩테스트 연습 > 2019 KAKAO BLIND RECRUITMENT > 길 찾기 게임

 

난이도: LEVEL3

알고리즘 유형: 이진 트리 구현 + 여러가지 순회 방법 

 

핵심 부분 

문제에서는 친절하게도 큰 힌트를 준다.

 

1. 해당 트리는 이진 트리 

2. 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
3. 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

 

y가 가장 큰 노드가 해당 이진 트리의 루트 노드 

레벨(깊이 / depth)은 y의 크기로 결정되며 크기가 클수록 레벨은 낮다. 

 

각 노드들이 좌표로 주어지는데 그럼 어떻게 이진 트리를 구현할 수 있을까? 

1. 이진 트리는 자식 노드를 최대 2개까지 가진다. 

2. 문제에서 주어진 특정 노드의 왼쪽/오른쪽 서브 트리 x 값을 활용

 

루트 노드 7을 보자 해당 좌표는 (8, 6)

다음 레벨인 노드 4 , 2 

여기서 어떤 노드가 왼쪽 노드인지 오른쪽 노드인지 판단할 수 있을까? x를 비교한다. 

8보다 x가 작은 노드4는 노드 7의 왼쪽 노드 8보다 x가 큰 노드2는 노드 7의 오른쪽 노드

 

여기까지는 쉽다 

하지만 레벨이 깊어지면 전 레벨 즉 레벨이 1개 낮은 레벨인 해당 노드의 부모 후보가 많아진다. 

ex) 6번 노드의 부모 후보 4, 2

ex) 8번 노드의 부모 후보 6, 1, 3

 

그럼 어떻게 판단을 할까? 

결국 탐색을 통한 판단을 해야 한다.

 

부모 노드부터 이번에 연결할 노드를 같이 parent, child로 주고 

왼쪽 오른쪽 결정을 하면서 내려가면서 

빈 왼쪽이나 빈 오른쪽 자리를 찾으면 끝난다. 

 

이렇게 차례대로 레벨 순서대로 채우면서 탐색을 해야 하니까

트리를 구현(노드를 연결)하기 전에 y의 크기를 기준으로 정렬을 해야 한다. 

 

참고 (정렬에 대한 내 생각)

자바에서 정렬을 할 때는 4가지 방법이 있는데

1번: Comparable 인터페이스를 상속받아서 Node 클래스에 정렬 방법을 오버라이딩 

2번: 정렬 클래스를 만들어서 Comparator 인터페이스를 상속하고 정렬할 때 해당 Comparator 넘기기 

3번: 익명 클래스를 통한 간단한 구현

4번: 람다 표현식을 통한 익명 클래스보다 더 간단한 구현 

 

이런 코테에서는 람다 표현식을 통해 간단하게 구현하는 게 좋을듯 하고 

실제 애플리케이션 비즈니스에서 많이 재사용되는 정렬 방식이라면 따로 Comparator를 만들어서 재사용하는 것도 좋을듯하다.  실제 실무에서는 어떻게 할지는 궁금하다. 

 

정답 코드 

import java.util.*;
class Solution {
    static class Node{
        int x; int y; int v;
        Node left; Node right;
        public Node (int x, int y, int v){
            this.x = x;
            this.y = y;
            this.v = v;
        }
    }
    static ArrayList<Node> nodes = new ArrayList<>();
    static int cnt = 0;
    static int [][] answer; 
    public int[][] solution(int[][] nodeinfo) {
        
        int size = nodeinfo.length;
        
        for(int i = 0; i < size; i++){
            nodes.add(new Node(nodeinfo[i][0], nodeinfo[i][1], i + 1));
        }
        
        // y 크기 내림차순 정렬 -> 레벨(depth) 오름차순 정렬  
        Collections.sort(nodes, (o1, o2) -> {
            return o2.y - o1.y;
        });
        
        Node root = nodes.get(0); // 루트 노드 꺼내기 
        for(int i = 1; i < size; i++){
            update(root, nodes.get(i));
        }
        answer = new int [2][size];
        pre(root);  // 전위 순회 시작 
        cnt = 0;    // cnt 초기화 
        post(root); // 후위 순회 시작 
        return answer;
    }
    public static void post(Node cur){ // 후위 순회
        if(cur.left != null){
            post(cur.left);
        }
        if(cur.right != null){
            post(cur.right);
        }
        answer[1][cnt++] = cur.v;
    }
    public static void pre(Node cur){ // 전위 순회
        answer[0][cnt++] = cur.v;
        if(cur.left != null){
            pre(cur.left);
        }
        if(cur.right != null){
            pre(cur.right);
        }
    }
    public static void update(Node parent, Node child){ // 노드 연결
        if(parent.x > child.x){ // 왼쪽
            if(parent.left == null) parent.left = child;
            else update(parent.left, child);
        }
        else{
            if(parent.right == null) parent.right = child;
            else update(parent.right, child);
        }
    }
}