문제

Programmers Lv3, 길 찾기 게임

핵심

• 입력의 크기가 10,000이라 대략 O(N^2)이하 알고리즘을 사용한다.
• 같은 레벨에 있는 노드는 같은 y좌표를 가지고, 임의의 노드 V 왼쪽 서브 트리에 있는 모든 노드 값은 V의 X값보다 적고, 오른쪽 서브 트리에 있는 모든 노드의 값은 V의 x값보다 큰 이진 트리를 구성해야 한다.
• 이진 트리로 구성했던 좌표가 임의의 순서로 주어지기 때문에 루트는 1개의 노드이고, 각 레벨에서 트리의 개수는 $2^{level} - 1$개가 보장된다.
  
• 이진 트리의 좌표가 주어질 때, 어떻게 이진 트리를 채워나가야 하는지가 핵심이다. 그림과 같은 이진 트리를 구성하기 위해선 레벨이 높은 트리부터 채운다. X좌표를 오름차순으로 정렬해야 할까? 정렬할 필요는 없다. 이진 트리를 채우는 과정에서 루트의 X보다 작다면 왼쪽, 크다면 오른쪽에 정렬되어 삽입되기 때문이다. 구체적인 동작 과정은 아래와 같다.
  • 루트 노드의 X좌표를 보고 삽입할 위치를 정한다.
  • 왼쪽 또는 오른쪽에 삽입한다. 만약 이미 삽입되어 있으면? 루트 왼쪽 자식을 기준으로 X좌표가 작다면 루트 왼쪽 자식에 왼쪽에, 더 크다면 오른쪽에 삽입한다. 만약 그 위치도 이미 삽입되어 있다면? 그 루트 왼쪽 자식의 왼쪽 자식에 왼쪽 또는 오른쪽에 삽입한다. 즉, 재귀로 구성하기 좋다는 것을 알 수 있다. 코드로 나타내면 아래와 같다.

void setParent(int pa_idx, int ch_idx, int ch_x, vector<vector<int>>& nodeinfo) {
    
    int pa_x = nodeinfo[pa_idx - 1][0];
        
    if (ch_x < pa_x) { // x의 길이가 더 짧으면 왼쪽에 삽입
        if (lc[pa_idx] == 0) { //  
            lc[pa_idx] = ch_idx;
        } 
        else {
            setParent(lc[pa_idx], ch_idx, ch_x, nodeinfo); // 비어 있지 않다면 해당 노드의 자식으로... 
        }
    } else { // x의 길이가 더 길면 오른쪽에 삽입
        if (rc[pa_idx] == 0) {
            rc[pa_idx] = ch_idx; 
        } 
        else {
            setParent(rc[pa_idx], ch_idx, ch_x, nodeinfo); // 비어 있지 않다면 해당 노드의 자식으로... 
        }
    }
}

• 배열을 이용한 트리를 만들었다. 왼쪽 자식과 오른쪽 자식을 배열에 저장한다. 예제의 경우 트리 배열을 저장하면 아래와 같이 담긴다.
  

root_idx = 7;
int lc[10'004] = {0, 0, 0, 0, 6, 0, 0, 4, 5, ...};
int rc[10'004] = {0, 8, 3, 0, 1, 0, 9, 2, 0, ...};

개선

코드

C++

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <tuple>

using namespace std;

int lc[10'004];
int rc[10'004];

void setParent(int pa_idx, int ch_idx, int ch_x, vector<vector<int>>& nodeinfo) {
    
    int pa_x = nodeinfo[pa_idx - 1][0];
        
    if (ch_x < pa_x) {
        if (lc[pa_idx] == 0) {
            lc[pa_idx] = ch_idx;
        } 
        else {
            setParent(lc[pa_idx], ch_idx, ch_x, nodeinfo);
        }
    } else {
        if (rc[pa_idx] == 0) {
            rc[pa_idx] = ch_idx;
        } 
        else {
            setParent(rc[pa_idx], ch_idx, ch_x, nodeinfo);
        }
    }
}

void preorder(int idx, vector<int>& ret) {
    if (idx == 0) return;
    
    ret.push_back(idx);
    preorder(lc[idx], ret);
    preorder(rc[idx], ret);
}

void postorder(int idx, vector<int>& ret) {
    if (idx == 0) return;
    
    postorder(lc[idx], ret);
    postorder(rc[idx], ret);
    ret.push_back(idx);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<tuple<int, int, int>> nodes;

    for (int i = 0; i < nodeinfo.size(); ++i) {
        nodes.push_back({i + 1, nodeinfo[i][0], nodeinfo[i][1]});
    }

    sort(nodes.begin(), nodes.end(), [](auto& a, auto& b) {
        if (get<2>(a) != get<2>(b)) {
            return get<2>(a) > get<2>(b);
        }
        return get<1>(a) < get<1>(b);
    });

    
    int root_idx = get<0>(nodes[0]);
    for (int i = 1; i < nodes.size(); ++i) {
        setParent(root_idx, get<0>(nodes[i]), get<1>(nodes[i]), nodeinfo);
    }

    vector<vector<int>> ans;
    vector<int> pre, post;
    
    preorder(root_idx, pre);
    postorder(root_idx, post);

    ans.push_back(pre);
    ans.push_back(post);

    return ans;
}

Java

import java.util.*;

class Solution {
    int[] lc = new int[10_004];
    int[] rc = new int[10_004];
    
    public void setParent(int paIdx, int chIdx, int chX, int[][] nodeinfo) {
        int paX = nodeinfo[paIdx - 1][0];

        if (chX < paX) {
            if (lc[paIdx] == 0) {
                lc[paIdx] = chIdx;
            } else {
                setParent(lc[paIdx], chIdx, chX, nodeinfo);
            }
        } else {
            if (rc[paIdx] == 0) {
                rc[paIdx] = chIdx;
            } else {
                setParent(rc[paIdx], chIdx, chX, nodeinfo);
            }
        }
    }

    public void preorder(int idx, List<Integer> ret) {
        if (idx == 0) return;
        ret.add(idx);
        preorder(lc[idx], ret);
        preorder(rc[idx], ret);
    }

    public void postorder(int idx, List<Integer> ret) {
        if (idx == 0) return;
        postorder(lc[idx], ret);
        postorder(rc[idx], ret);
        ret.add(idx);
    }

    public int[][] solution(int[][] nodeinfo) {
        List<int[]> nodes = new ArrayList<>();
        for (int i = 0; i < nodeinfo.length; ++i) {
            nodes.add(new int[]{i + 1, nodeinfo[i][0], nodeinfo[i][1]});
        }

        nodes.sort((a, b) -> b[2] - a[2]);

        int rootIdx = nodes.get(0)[0];
        for (int i = 1; i < nodes.size(); ++i) {
            setParent(rootIdx, nodes.get(i)[0], nodes.get(i)[1], nodeinfo);
        }

        List<Integer> pre = new ArrayList<>();
        List<Integer> post = new ArrayList<>();
        
        preorder(rootIdx, pre);
        postorder(rootIdx, post);

        int[][] ans = new int[2][];
        ans[0] = pre.stream().mapToInt(i -> i).toArray();
        ans[1] = post.stream().mapToInt(i -> i).toArray();
        
        return ans;
    }
}