[BOJ] 2493 - 탑

문제 링크

알바하면서 푸느라 컴파일 에러를 무려 세 번이나 냈다. 집에 와서 컴파일해보니 우선순위 큐에서 원소를 top()으로 불러오지도 않고 second를 불러오고 세미콜론도 빼먹고 아주 가관..
처음에는 문제를 제대로 이해하지 않고 그냥 왼쪽부터 훑으면서 높이가 가장 최대인 지점만 알면 되겠네? 하고 짰다가 틀렸다.
다시 생각해보니 나보다 큰 건물은 반드시 높이가 최대가 아닐수도 있으므로 배열에 저장해두고 잘 풀어야 하는 것이었다.
분명 어디선가 많이 봤던 문제인 것 같아 무난한 풀이법으로 풀었다.
우선 최소높이인 건물부터 확인하여 나보다 왼쪽에 건물이 남아있는지 확인하고 확인이 끝나면 그 건물을 지워주면 되므로 펜윅트리를 이용해 업데이트 하는 방식을 사용했다.
펜윅트리는 사랑이다. 핸드폰으로도 n분안에 구현 가능한 펜윅트리 하세여 여러분 세그였다면 분명 알바 끝날때까지 구현이 끝나지 않았을거야..
그럼 이제 나의 왼쪽에서 가장 가까운 건물의 위치가 어디냐를 찾아야 하는데.. 그냥 어렵게 생각 안하고 이분탐색으로 찾으면 한 번 찾는데 O(logN) 찾는 과정이 O(logN)이므로 시간복잡도가 O(logN*logN)이 되니 매우 널널해서 그렇게 찾기로 했다. 맞은걸 보면 아마 틀린 접근은 아니었나보다

소스코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
typedef pair<int, int> PII;

priority_queue<PII> pq;
int tree[500005], num[500005];

void update(int val, int i) {
    while (i < 500005) {
        tree[i] += val;
        i += i & -i;
    }
}

int find(int i) {
    int rtn = 0;
    while (i > 0) {
        rtn += tree[i];
        i -= i & -i;
    }
    return rtn;
}

int main(void) {
    int n, mx = 0, idx = 0, a;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a);
        update(1, i);
        pq.push({ -a, i });
    }

    while (!pq.empty()) {
        int now = pq.top().second;
        pq.pop();
        update(-1, now);
        if (find(now - 1) == 0) {
            num[now] = 0;
        }
        else {
            int L = 1, R = now - 1;
            while (true) {
                int mid = (L + R) / 2;
                bool ck = (find(R) - find(mid)) == 0;
                if (mid == L) {
                    if (!ck) L = R;
                    break;
                }
                if (!ck)
                    L = mid;
                else R = mid;
            }
            num[now] = L;
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", num[i]);
    return 0;
}