[PS] 이진 검색 트리 복원하기 / C++ (백준 32028번)

2024 UCPC 예선 D번 문제로, 팀원이 아쉽게 해결하지 못한 문제였다. 대회가 끝나고 풀어보니 본인도 2시간 넘게 걸렸다..

 

해결 방법

 사실 이분 탐색, 자료 구조를 활용한 트리를 만드는 구현 문제에 가까운데 너무 복잡하다. 정리하는데 노트가 2장...

1. 입력에서 받는 노드 정보를 저장해 놓고, 노드의 깊이($H_{i}$)를 기준으로 정렬한다.

2. 깊이가 낮은 노드(root)부터 시작하여 모든 노드의 위치를 구한다.

• 이때, 내 부모 노드에 저장된 값을 바탕으로 해당 노드의 자식이 될 노드들의 최솟값과 최댓값을 구하여 저장한다.
• ex. root노드의 왼쪽 자식 노드인 n노드가 있다 가정하면, n노드의 왼쪽 자식들은 n노드의 값보다 작아야 하며, 오른쪽 자식 노드들은 n노드의 값과 큼과 동시에 root노드의 값보다 작아야 한다.

3. 이렇게 모든 노드들이 조건에 맞게 저장된 결과를 입력에서 받아 저장해 놓은 노드 정보를 바탕으로 이분 탐색으로 찾아서 출력해 주면 된다. 이것 때문에 코드가 아주 더러워졌다 

 

여하튼 자료구조를 적절히 사용하여 $H_{i}$를 기준으로 정렬하여 각 노드가 들어갈 수 있는 곳을 찾는 로직만 잘 짜면 쉽게(?) 풀 수 있는 구현 문제이다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
vector < pair<int, pair<int, int>>> vec;
pair<int, int> pa[200001], d[200001], range[200001];
bool cmp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b){
    if (a.second.second == b.second.second)return a.second.first < b.second.first;
    return a.second.second < b.second.second;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int ai, hi;
        scanf("%d %d", &ai, &hi);
        d[i] = make_pair(ai, hi);
        pair<int, pair<int, int>> pa;
        pa.first = i; pa.second.first = ai; pa.second.second = hi;
        vec.push_back(pa);
        range[i - 1].first = -2e9 - 1;
        range[i - 1].second = 2e9 + 1;
    }
    sort(vec.begin(), vec.end(), cmp);
    if (vec[0].second.second != 1) {
        printf("-1\n");
        return 0;
    }
    deque<int> deq;
    deq.push_back(0);
    
    for (int i = 1; i < n; i++) {
        int ai = vec[i].second.first, hi = vec[i].second.second;
        while (1) {
            if (deq.empty()) {
                printf("-1\n");
                return 0;
            }
            int top = deq.front();
            if (vec[top].second.second == hi) {
                printf("-1\n");
                return 0;
            }
            else if (hi - vec[top].second.second > 1) {
                deq.pop_front();
            }
            else if (vec[top].second.second == hi - 1) {
                if (range[top].first < ai && ai < vec[top].second.first && pa[top].first == 0) {
                    pa[top].first = i;
                    deq.push_back(i);
                    range[i].first = range[top].first;
                    range[i].second = vec[top].second.first;
                    break;
                }
                else if (vec[top].second.first < ai && ai < range[top].second && pa[top].second == 0) {
                    pa[top].second = i;
                    deq.push_back(i);
                    range[i].first = vec[top].second.first;
                    range[i].second = range[top].second;
                    deq.pop_front();
                    break;
                }
                else {
                    deq.pop_front();
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        int st = 0, en = n - 1, mid;
        while (st<=en) {
            mid = (st + en) / 2;
            int vec_ai = vec[mid].second.first, vec_hi = vec[mid].second.second;
            if (vec_hi == d[i].second) {
                if (vec_ai == d[i].first) {
                    break;
                }
                else if(vec_ai > d[i].first){
                    en = mid - 1;
                }
                else {
                    st = mid + 1;
                }
            }
            else if(vec_hi > d[i].second) {
                en = mid - 1;
            }
            else {
                st = mid + 1;
            }
        }
        printf("%d %d\n", pa[mid].first?vec[pa[mid].first].first:-1, pa[mid].second?vec[pa[mid].second].first:-1);
    }
    return 0;
}