[BOJ / C++] 홍익 투어리스트 (이진검색트리)

문제링크: https://www.acmicpc.net/problem/23326

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n, q;
    cin >> n >> q;

    set<int> S;
    for (int i = 1; i <= n; i++) {
        int inp;
        cin >> inp;

        if (inp == 1) S.insert(i);
    }

    int cur = 1;
    while (q--) {
        int op;
        cin >> op;

        if (op == 1) {
            int i;
            cin >> i;

            auto it = S.find(i);
            if (it == S.end()) {
                S.insert(i);
            }
            else {
                S.erase(i);
            }
        }
        else if (op == 2) {
            int x;
            cin >> x;

            cur = (cur - 1 + x) % n + 1;
        }
        else if (op == 3) {
            if (S.empty()) {
                cout << -1 << '\n';
            }
            else {
                auto it = S.lower_bound(cur);
                if (it != S.end()) {
                    cout << *it - cur << '\n';
                }
                else {
                    cout << *(S.begin()) + (n - cur) << '\n';
                }
            }
        }
    }

}

 

 

2. 시간복잡도

n = 5 * 10^5 이고, q = 10^5이다. 각 op에 대한 연산이 O(qn)에 되면 시간초과가 나므로 O(qlgn)으로 만들어야한다. op == 1에서 insert, erase는 lgn이 소요되고, op==2의 인덱스 계산은 O(1)에 가능하다. op==3에서 lower_bound는 lgn에 가능하므로 총 O(qlgn)에 처리가 가능하다.

10^5 * 20 < 10^8 이므로 시간제한 1초 내에 통과 가능하다.

 

 

3. 분석

명소 인덱스만을 set에 집어 넣는 것이 핵심이다. set을 활용하면 이진검색트리이므로 insert, erase가 모두 lgn에 처리가 된다. 만약 vector를 사용한다면 erase에 O(n)이 걸려서 시간초과가 된다. 

이 문제는 1-index 이므로 op==2일 때 cur-1로 먼저 0-index로 맞춰준 다음 x를 더한 후 % n을 해주고 나서 +1로 다시 1-index로 바꿔주면 된다. 

op==3에서 비어있는지 확인해준 후, lower_bound가 없으면 다음에 S.begin()이 가장 가까운 명소가 된다. 왜냐하면 S가 명소의 인덱스만 가지고 있기 때문이다.