[백준 23326] 홍익 투어리스트

이 문제는 문제 리스트를 배열이나 벡터로 관리하면 안된다.

단순히 명소를 지정하고 해제하는 정도는 배열로 충분히 처리가 가능하지만, 3번 연산을 수행하려면 가장 가까운 오른쪽 명소를 찾기 위해서 $O(N)$의 시간 복잡도가 필요하다.

따라서, 전체 시간 복잡도는 $O(N^2)$가 되므로 시간 초과가 발생한다.

그렇다면, 어떤 자료구조를 선택해야할까?

연결 리스트도 배열과 같은 논리로 불가능하고, 스택・큐・덱은 특정 위치에 가장 가까운 명소를 찾는데는 큰 도움이 되지 않는다. 스택이나 큐는 random-access 자체가 불가능하고 덱은 random-access는 가능한데, 배열처럼 시간 복잡도가 $O(N)$이 되서 불가능하다.

이진 탐색트리로 관리하면, 인접한 명소를 찾는데 용이하고, 삽입과 삭제도 log-scale로 처리가 가능하다.
따라서, 명소는 set으로 관리해주면 된다.

위치가 1 ~ N이므로 이를 0 ~ N-1로 대응 시킨뒤 모듈러 연산으로 대응 지점을 구한 뒤 다시 1 ~ N으로 복귀 시키면 된다.
이는 cur = (cur + x - 1) % n + 1이 된다는 의미이다.

만약, 명소에 도달하기 위해 시계방향으로 움직여야하는 최소 거리는 문제 조건처럼 att.empty()면 -1을 출력하고, att.lower_bound(cur)로 cur이후에 있는 명소를 찾을 수 있다.

하지만, att.end()가 리턴될 수 있는데, 이는 구역이 원형으로 배치되어 있기 때문에 한 바퀴를 더 돌아att.begin()으로 가는 것이 최소 거리임을 알 수 있다.

이를 코드로 옮기면 AC를 받을 수 있다.

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

int n, q, cur = 1;
set<int> att;

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

	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		bool isAtt;
		cin >> isAtt;
		if (isAtt) att.insert(i);
	}

	while (q--) {
		int c;
		cin >> c;
		if (c == 1) {
			int i;
			cin >> i;
			if (att.find(i) != att.end()) att.erase(i);
			else att.insert(i);
		} else if (c == 2) {
			int x;
			cin >> x;
			cur = (cur + x - 1) % n + 1;
		} else {
			if (att.empty()) {
				cout << -1 << "\n";
				continue;
			}
			auto it = att.lower_bound(cur);
			if (it == att.end()) it = att.begin();
			int dist = *it - cur;
			if (dist < 0) dist += n;
			cout << dist << "\n";
		}
	}
}