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

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

 

문제

---

도현이는 홍익 투어리스트가 되어 홍익대학교를 견학하려고 한다. 홍익대학교는 𝑁개의 구역이 원형으로 배치된 모습이다. 1번 구역에서 시계 방향으로 각각 2번, ... , 𝑁번 구역이 존재하고, 𝑁번 구역에서 시계 방향으로 한 칸 더 갈 경우 1번 구역으로 도착한다. 

홍익대학교에는 명소가 존재한다. 도현이는 알찬 투어를 위해 명소만을 방문하려 한다. 도현이는 1번 구역에 서있다.

도현이를 위해 다음과 같은 쿼리를 수행하는 프로그램을 작성해보자.

•  1 𝑖 : 𝑖번 구역이 명소가 아니었다면 명소로 지정되고, 명소였다면 지정이 풀리게 된다. (1 ≤ 𝑖 ≤ 𝑁)
•  2 𝑥 : 도현이가 시계방향으로 𝑥만큼 이동한다. (1 ≤ 𝑥 ≤ 10⁹)
•  3 : 도현이가 명소에 도달하기 위해 시계방향으로 최소 몇 칸 움직여야 하는 지 출력한다. 명소가 존재하지 않는 경우 −1을 출력한다.

 

입력

---

 

첫째 줄에 구역의 개수 𝑁 (1 ≤ 𝑁 ≤ 500000)과 쿼리의 개수 𝑄 (1 ≤ 𝑄 ≤ 100000)가 정수로 주어진다.

둘째 줄에 길이 𝑁의 수열 𝐴가 주어진다. 𝑖번째 구역이 명소라면 𝐴_𝑖는 1, 그렇지 않다면 0이다.

셋째 줄부터 𝑄줄에 걸쳐 본문의 쿼리가 주어진다. 3번 쿼리는 하나 이상 존재한다.

 

출력

---

 3번 쿼리가 주어질 때마다 해당 쿼리의 값을 출력한다.

 

문제 풀이

---

set을 이용하는 문제.

명소만을 저장하는 set을 만들어 초기 상태를 저장한다.

1번 쿼리가 주어지면 set에 존재하는지 확인하여 존재하지 않는다면(=아직 명소가 아닌 상태) insert로 set에 저장한다. 존재한다면(=현재 명소인 상태) erase로 set에서 빼낸다.

2번 쿼리는 현재 위치를 저장하는 변수에 이동 칸 수만큼 더해 나중에 3번 쿼리에 사용할 수 있게 한다.

3번 쿼리는 set의 내장함수 lower_bound를 사용한다. 현재 위치와 같거나 큰 값을 가지는 iterator를 반환하므로 해당 iterator가 가지는 값에서 현재 위치를 빼면 몇 칸 이동해야 하는지를 구할 수 있다.

algorithm헤더의 lower_bound는 set이나 map처럼 random access가 불가능한 컨테이너는 O(N)의 시간복잡도를 가지기 때문에 시간 초과가 발생한다.

 

아래는 코드.

#include <iostream>
#include <set>
using namespace std;

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

	int N, Q;
	int tf, query, num;
	int currentPos = 0;
	set<int> landmarks;
	set<int>::iterator it;
	cin >> N >> Q;
	for (int i = 0; i < N; i++)
	{
		cin >> tf;
		if (tf == 1)
		{
			landmarks.insert(i);
		}
	}
	for (int i = 0; i < Q; i++)
	{
		cin >> query;
		if (query == 1)
		{
			cin >> num;
			it = landmarks.find(num - 1);
			if (it == landmarks.end())
			{
				landmarks.insert(num - 1);
			}
			else
			{
				landmarks.erase(it);
			}
		}
		else if (query == 2)
		{
			cin >> num;
			currentPos = ((currentPos + num) % N);
		}
		else
		{
			if (landmarks.size() == 0)
			{
				cout << -1 << "\n";
			}
			else
			{
				it = landmarks.lower_bound(currentPos);
				if (it == landmarks.end())
				{
					int moveCountToBegin = N - currentPos;
					cout << *landmarks.begin() + moveCountToBegin << "\n";
				}
				else
				{
					cout << *it - currentPos << "\n";
				}
			}
		}
	}
	return 0;
}