[G3] 백준 23326번 홍익 투어리스트 C++ 이분 탐색, 집합, set, lower_bound

리뷰

 

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

원형으로 된 구조에서 쿼리에 따른 결과를 수행하고 출력하는 문제

 

 

전역 변수

• n : 구역의 개수를 저장할 변수
• q : 쿼리의 개수를 저장할 변수
• d : 명소로 지정된 구역을 저장할 집합

 

함수

없음

 

 

문제풀이

1. n, q값을 입력 받고, n개의 구역이 명소인지 여부를 입력 받아 명소인 구역의 번호를 d에 삽입해준다.
2. 변수 x를 1로 초기화 하고, q번의 while루프를 수행하고, 매 루프마다 변수 c에 쿼리 번호를 입력 받는다.
3. c가 1일 경우 변수 i에 구역 번호를 입력 받고, d에 i가 존재하면 지우고, 아니라면 추가한다.
4. c가 2일 경우 변수 p에 이동할 길이를 입력 받고, n으로 나눈 나머지를 다시 p에 대입한다.
5. x+p가 n으로 나누어 떨어지면 n을, 아니라면 x+p를 n으로 나눈 나머지를 x에 대입한다.
6. c가 3일 경우 d가 빈 상태라면 -1을 출력 후 개행문자를 삽입한다.
7. d가 비지 않은 경우 변수 back에 lower_bound멤버 함수를 통해 x이상인 첫번째 요소의 반복자를 저장한다.
8. back이 d의 end()가 아닐 경우 back의 실제 값에서 x를 뺀 값을 출력 후 개행문자를 삽입한다.
9. back이 d의 end()일 경우 변수 front에 d의 begin()의 반복자를 저장한다.
10. n-x+front의 실제 값을 출력 후 개행문자를 삽입한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. N의 범위가 최대 50만이고, 쿼리의 개수가 최대 10만이므로 O(LogN)의 시간복잡도로 접근해야 한다.
2. 자료구조로 set을 사용할 경우 자동으로 정렬되며 lower_bound를 멤버 함수로 사용할 수 있다.

 

정답 코드

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

int n, q;
set<int> d;

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

	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		int v; cin >> v;
		if (v) d.insert(i);
	}

	int x = 1;
	while (q--) {
		int c; cin >> c;
		if (c == 1) {
			int i; cin >> i;
			if (d.count(i)) d.erase(i);
			else d.insert(i);
		}
		else if (c == 2) {
			int p; cin >> p;
			x = (x + p) % n ? (x + p) % n : n;
		}
		else {
			if (d.empty()) cout << -1 << "\n";
			else {
				auto back = d.lower_bound(x);
				if (back != d.end()) cout << *back - x << "\n";
				else {
					auto front = d.begin();
					cout << n - x + *front << "\n";
				}
			}
		}
		//cout << "x : " << x << "\n";
	}
}