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

1. 문제

---

프로그래머스

 

2. 풀이 과정

---

문제에는 다음과 같은 조건이 존재한다.

그 중에서도

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

이 부분은 이진 탐색 트리를 의미한다. 

즉, 이 문제는 x좌표를 값으로 하는 이진 탐색 트리를 만든 뒤, 전위 순회, 후위 순회를 하면 된다.

 

하지만 여기서 주의해야 할점이 있다.

첫번째는, 트리에는 x좌표의 값이 아닌 노드의 번호(=인덱스)가 들어간다는 것이다.

그렇기 때문에 이진탐색트리에 데이터를 삽입할 때는 x좌표 값을 기준으로 비교해야 하지만 실제 값은 이 x좌표 값이 아닌 노드의 번호가 들어가야 한다. 

 

두번째는, 이진 탐색 트리의 특성이다.

이진 탐색 트리는 같은 데이터 셋이라도 데이터를 삽입하는 순서에 따라 그 모양이 완전히 달라진다.

문제에서 좌표값들이 루트에서부터 순서대로 주어진다는 말은 없으니 직접 정렬을 해줘야 한다는 의미이다.

 

이 두가지를 유의하면서 문제를 풀면된다.

 

과정은 다음과 같다. 

 

1. 노드들을 y좌표를 기준으로 정렬한다.

만약 y좌표가 같다면 x좌표를 기준으로 정렬한다.

 

2. 이진 탐색 트리를 만들어 데이터를 삽입한다.

이진 탐색 트리에 데이터를 삽입할 때 x좌표 값과 인덱스 값을 적절히 사용해 삽입해야 한다.

 

3. 전위 순회와 후위 순회를 한다.

 

바로 코드를 보자

3. 내 코드

---

import java.util.*;
class Solution {
    
    class Node {
        int key;
        int value;
        Node left;
        Node right;
        
        Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }
    
    class BST{
        Node root;
        
        BST() {
            root = null;
        }
        
        void insert(int value, int key) {
            root = insertRec(root, value, key);
        }
        
        Node insertRec(Node root, int value, int key) {
            if(root == null) {
                return new Node(key, value);
            }
            
            if(root.value > value) {
                root.left = insertRec(root.left, value, key);
            } else if(root.value < value) {
                root.right = insertRec(root.right, value, key);
            }
            
            return root;
        }
        
        void preOrder(List<Integer> visitOrder) {
            preOrderRec(root, visitOrder);
        }
        
        void preOrderRec(Node root, List<Integer> visitOrder) {
            if(root == null) {
                return;
            }
            visitOrder.add(root.key);
            preOrderRec(root.left, visitOrder);
            preOrderRec(root.right, visitOrder);
        }
        
        void postOrder(List<Integer> visitOrder) {
            postOrderRec(root, visitOrder);
        }
        
        void postOrderRec(Node root, List<Integer> visitOrder) {
            if(root == null) {
                return;
            }
            postOrderRec(root.left, visitOrder);
            postOrderRec(root.right, visitOrder);
            visitOrder.add(root.key);
        }
        
    }
    
    class Point{
        int x, y;
        
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
    }
    public int[][] solution(int[][] nodeinfo) {
        
        // 1. 노드 번호 - 좌표 맵 정의
        HashMap<Integer, Point> map = new HashMap<>();
        for(int i = 0; i < nodeinfo.length; i++) {
            map.put(i + 1, new Point(nodeinfo[i][0], nodeinfo[i][1]));
        }
        
        // 2. 좌표 정렬
        List<Map.Entry<Integer, Point>> entrySet = new ArrayList<>(map.entrySet());
        entrySet.sort((d1, d2) -> {
            if(d2.getValue().y == d1.getValue().y){
                return Integer.compare(d2.getValue().x, d1.getValue().x);
            }
            return Integer.compare(d2.getValue().y, d1.getValue().y);
        });
        
        List<Integer> node_list = new ArrayList<>();
        
        for(Map.Entry<Integer, Point> entry: entrySet) {
            node_list.add(entry.getKey());
        }
        
        // 3. x좌표 리스트 만들기
        List<Integer> x_list = new ArrayList<>();
        x_list.add(-1); // 노드는 1번부터 이므로 0번에 더미값 넣기
        for(int i = 0; i < nodeinfo.length; i++) {
            x_list.add(nodeinfo[i][0]); // x좌표 
        }
        
        // 4. 이진탐색트리 만들기
        BST bst = new BST();
        
        for(int node_num: node_list) {
            bst.insert(x_list.get(node_num), node_num);
        }
        
        int[][] answer = new int[2][node_list.size()];
        // 5. 전위 순회하기
        List<Integer> visit_order = new ArrayList<>();
        bst.preOrder(visit_order);
        answer[0] = visit_order.stream().mapToInt(i -> i.intValue()).toArray();
        
        // 6. 후위 순회하기
        visit_order = new ArrayList<>();
        bst.postOrder(visit_order);
        answer[1] = visit_order.stream().mapToInt(i -> i.intValue()).toArray();
        
        return answer;
    }
    
    
}

시간 복잡도

• 평균: O(NlogN)
• 최악: O(N^2)

이진탐색트리가 한쪽으로 치우쳐져 삽입되는 경우에 시간복잡도가 O(N^2)까지 증가할 수 있다.

 

class Node {
    int key;
    int value;
    Node left;
    Node right;

    Node(int key, int value) {
        this.key = key;
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

Node insertRec(Node root, int value, int key) {
    if(root == null) {
        return new Node(key, value);
    }

    if(root.value > value) {
        root.left = insertRec(root.left, value, key);
    } else if(root.value < value) {
        root.right = insertRec(root.right, value, key);
    }

    return root;
}

노드 클래스에 인덱스 번호(key)와 x좌표(value)를 함께 포함시켜 비교는 x좌표로, 저장은 인덱스 번호로 수행했다.

 

4. 피드백

---

• 이진탐색트리를 구현방식(value는 일반적인 경우에는 필요없음)

class Node {
    int key;
    int value;
    Node left;
    Node right;

    Node(int key, int value) {
        this.key = key;
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BST{
    Node root;

    BST() {
        root = null;
    }

    void insert(int value, int key) {
        root = insertRec(root, value, key);
    }

    Node insertRec(Node root, int value, int key) {
        if(root == null) {
            return new Node(key, value);
        }

        if(root.value > value) {
            root.left = insertRec(root.left, value, key);
        } else if(root.value < value) {
            root.right = insertRec(root.right, value, key);
        }

        return root;
    }

    void preOrder(List<Integer> visitOrder) {
        preOrderRec(root, visitOrder);
    }

    void preOrderRec(Node root, List<Integer> visitOrder) {
        if(root == null) {
            return;
        }
        visitOrder.add(root.key);
        preOrderRec(root.left, visitOrder);
        preOrderRec(root.right, visitOrder);
    }

    void postOrder(List<Integer> visitOrder) {
        postOrderRec(root, visitOrder);
    }

    void postOrderRec(Node root, List<Integer> visitOrder) {
        if(root == null) {
            return;
        }
        postOrderRec(root.left, visitOrder);
        postOrderRec(root.right, visitOrder);
        visitOrder.add(root.key);
    }

}

 

• 해시맵에서 value값을 기준으로 정렬하고 key값 리스트로 뽑아내기

// 2. 좌표 정렬
List<Map.Entry<Integer, Point>> entrySet = new ArrayList<>(map.entrySet());
entrySet.sort((d1, d2) -> {
    if(d2.getValue().y == d1.getValue().y){
        return Integer.compare(d2.getValue().x, d1.getValue().x);
    }
    return Integer.compare(d2.getValue().y, d1.getValue().y);
});

List<Integer> node_list = new ArrayList<>();

for(Map.Entry<Integer, Point> entry: entrySet) {
    node_list.add(entry.getKey());
}

생각보다 활용도가 높으니 외워두면 좋을 것 같다.