Today I Learned

오늘도 주말에 있을 코딩테스트를 대비하기 위해 코테 문제를 풀었다. 주말에 2시부터 7시까지 풀어야되는데 체력이 될 지 모르겠다. ide와 웹 검색까지 허용해주는 코테라서 오히려 더 어려울 것 같다. 열심히 해보자!!

길 찾기 게임

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

문제

트리에 대해 다음의 조건이 주어진다.


1. 트리를 구성하는 모든 노드의 x,y좌표는 정수다.
2. 모든 노드는 서로 다른 x값을 가진다.
3. 같은 level의 노드는 y값이 같다.
4. 자식 노드의 y값은 항상 부모보다 작다.
5. 모든 노드에서 루트의 x값은 왼쪽 자식의 x값보다 크고, 오른쪽 자식의 x값보다 작다.
모든 노드의 정보다 nodeinfo 배열에 담겨서 매개변수로 주어진다. 해당 노드들로 구성된 이진트리의 전위 순회, 후위순회 한 결과를 2차원 배열에 담아 return해라.

제약조건
nodeinfo의 길이는 1이상 10000이하.
nodeinfo[i]는 x좌표, y좌표 순으로 들어있다.
모든 노드의 좌표는 0이상 100000이하인 정수이며 트리의 깊이는 1000이하이다.
모든 노드는 주어진 규칙을 지키며 잘못된 경우는 없다.

풀이 과정

트리를 구성하고 전위순회, 후위순회 메서드를 구현해 실행시켜 순서대로 반환만 하면 되는 간단한 문제이지만 구현 과정이 복잡하고 길어 시간이 꽤 소모되었다.

1. 우선 노드 클래스를 만든다. 추후 정렬을 할 예정이므로 Comparable을 구현해 compareTo 메서드를 오버라이드 해서 기본 정렬 기준을 구현해둔다. 기준은 y값이 같으면 x가 작은 순서대로, 아니면 y값이 큰 대로 정렬해 주어진 조건에 만족하게 정렬시킨다.

2. insert 메서드를 만든다. 부모와 자식노드로 명명한 매개변수를 받아 부모의 x값이 클 때, 왼쪽 자식이 비어있으면 넣고, 아니면 왼쪽 자식과 재귀로 다시 insert를 넣어준다. 부모의 x값이 크지 않으면 오른쪽 자식과 같은 방법으로 구현한다.

3. 노드 배열을 하나 만들어서 nodeinfo에 담긴 노드들의 정보를 토대로 노드를 생성해 배열에 넣어둔다. 그리고 Node의 compareTo를 통해 정렬 기준이 정해진 대로 노드 배열의 sort를 실행한다. 이렇게 되면 y값이 가장 큰 루트 노드가 가장 앞에 오고 왼쪽 자식, 오른쪽 자식순으로 level 별로 정렬된다.

4. 정렬된 노드 배열에서 루트노드와 비교해 insert 메서드를 실행시킨다. 이렇게 되면 Node의 left와 right Node들이 채워진다.

5. 전위순회와 후위순회 메서드를 구현한다. 전위순회는 루트-왼쪽-오른쪽순서대로 재귀함수를 통해 구현한다. 후위순회는 왼쪽-오른쪽-루트 순서대로 재귀함수를 통해 구현한다.

6. index값을 전역으로 설정해 0으로 만들고 전위순회, 0으로 다시 만들고 후위순회를 돌려 answer 2차원 배열에 담은 후 return하면 완료!

Java 코드

import java.util.*;
class Solution {
    int[][] answer;
    int index;
    
    public class Node implements Comparable<Node>{
        int x;
        int y;
        int value;
        Node left;
        Node right;
        
        // y값이 큰 순서대로 정렬. y가 같으면 x가 작은 순서대로 정렬
        @Override
        public int compareTo(Node other){
            if(this.y == other.y) {
                return this.x - other.x;
            } else {
                return other.y - this.y;
            }
        }
        
        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;
        }
    }
    
    public void insert(Node parent, Node child){
        if(parent.x > child.x){
            if(parent.left == null){
                parent.left = child;
            } else {
                insert(parent.left, child);
                }
        } else {
            if(parent.right == null){
                parent.right = child;
            } else {
                insert(parent.right, child);
            }
        }
    }
    
    
    public int[][] solution(int[][] nodeinfo) {
        Node[] nodes = new Node[nodeinfo.length];
        
        for(int i=0; i<nodeinfo.length; i++){
            nodes[i] = new Node(nodeinfo[i][0], nodeinfo[i][1], i+1, null, null);
        }
        Arrays.sort(nodes);
        
        Node root = nodes[0];
        for(int i=1; i<nodes.length; i++){
            insert(root, nodes[i]);
        }
        
        answer = new int[2][nodeinfo.length];
        index = 0;
        preorder(root);
        index = 0;
        postorder(root);

        return answer;
    }
    
    // 전위 순회
    public void preorder(Node root){
        if(root==null) return;
        answer[0][index++] = root.value;
        preorder(root.left);
        preorder(root.right);
    }
    
    // 후위순회
    public void postorder(Node root){
        if(root==null) return;
        postorder(root.left);
        postorder(root.right);
        answer[1][index++] = root.value;
    }
}