https://www.acmicpc.net/problem/23326
23326번: 홍익 투어리스트
도현이는 홍익 투어리스트가 되어 홍익대학교를 견학하려고 한다. 홍익대학교는 $N$개의 구역이 원형으로 배치된 모습이다. $1$번 구역에서 시계 방향으로 각각 $2$번, ... , $N$번 구역이 존재하고,
www.acmicpc.net
홍익 투어리스트 문제는 이진 검색 트리를 이용하여 해결할 수 있습니다.
명소의 위치만 이진 검색 트리에 저장해주면 됩니다.
- 1번 연산 : 이진 검색 트리에 존재한다면, 제거하고, 존재하지 않는다면, 명소로 추가,
시간 복잡도 : O(logN) - 2번 연산 : 도현이의 위치만 이동,
시간 복잡도 : O(1) - 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
'Algorithm > Binary Search Tree' 카테고리의 다른 글
[백준 19700번] 수업 (C++) (0) | 2022.06.01 |
---|---|
[백준 21939번] 문제 추천 시스템 Version 1 (C++) (0) | 2022.05.29 |
[백준 1202번] 보석 도둑 (C++) (0) | 2022.05.29 |