[백준 23326번] 홍대 투어리스트 (C++)

https://www.acmicpc.net/problem/23326

23326번: 홍익 투어리스트

---

홍익 투어리스트 문제는 이진 검색 트리를 이용하여 해결할 수 있습니다.

 

명소의 위치만 이진 검색 트리에 저장해주면 됩니다.

1. 1번 연산 : 이진 검색 트리에 존재한다면, 제거하고, 존재하지 않는다면, 명소로 추가, 시간 복잡도 : O(logN)
2. 2번 연산 : 도현이의 위치만 이동, 시간 복잡도 : O(1)
3. 3번 연산 : lower_bound()를 이용하여, 가장 가까운 명소의 위치를 계산, 시간 복잡도 : O(logN)

⚠️ 도현이의 위치를 이동시킬 때, 명소의 위치를 0-based로 해야 MOD 연산을 더 편하게 사용할 수 있습니다.

 

아래는 전체 코드입니다.

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

map<int, bool> m;   // map

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

    int n, q; cin >> n >> q;
    for(int i = 0; i < n; i++){
        bool b; cin >> b;
        if(b) m[i] = b; // 명소의 위치만 저장
    }

    int cur = 0; // 도현이의 위치
    for(int i = 0; i < q; i++){
        int query; cin >> query;

        if(query == 1){ // 1번 연산
            int x; cin >> x;
            if(m[x - 1]) m.erase(x - 1);
            else m[x - 1] = true;
        }else if(query == 2){   // 2번 연산
            int x; cin >> x;
            cur = (cur + x) % n;    // MOD 연산으로 도현이의 위치 이동시킴
        }else{  // 3번 연산
            if(m.size() == 0) // 명소가 없는 경우
                cout << - 1 << "\n";    // -1 출력
            else {
                auto pos = m.lower_bound(cur);    // 도현이 다음의 명소의 위치
                if(pos == m.end()){   // 도현이 이후에 명소가 없는 경우
                    int step = (n - cur) + (*m.begin()).first; // 첫번째 명소까지의 거리
                    cout << step << "\n"; // 다음 명소는 첫번째 명소
                }else{  // 도현이 이후에 명소가 있는 경우
                    cout << (*pos).first - cur << "\n"; // 명소의 위치 - 도현이의 위치
                }
            }
        }
    }
}

 

아래는 문제 풀이에 사용된 테스트케이스입니다.

5 1
1 1 1 1 1
3

5 2
0 1 1 1 1
2 10
3

5 2
0 1 0 1 1
2 10
3