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

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

 

본론부터 말하면 실패했다. ( 인터넷 참고 )

 

분류 : 자료 구조, 이분 탐색, 트리를 사용한 집합과 맵 

 

제한 : 1초, 1024MB

 

 

[생각했던거]

솔직히, 문제를 보고 어떻게 풀어야할지 감이 잘 안왔다. 억지로 큐를 만들어서 Before, after 나눠두고 계속 옮기는 식으로 진행하려 했는데, 이렇게 되면, after 큐에서 before 큐로 옮긴 뒤에 한 바퀴 돌면 before에서 다시 해줘야 하는데 그거 옮기는 과정이 번거로워졌다. 그래서 풀지는 못하고 인터넷 서칭 했음.

 

 

 

 

 

 

[설명]

우선, set을 사용해서 푸는 문제였다. 분류에 이분탐색이 나와있는데,  C++ 에서 set은

BST 기반으로 중위 순회로 동작하여 정렬과 탐색이 빠르다.

 

[정리]

set은 erase, insert를 사용하고, find를 이용해서 빠르게 탐색할 수 있다. ( location.end())  가 false 조건. 

set은 고유한 upper_bound, lower_bound를 갖는다. algorithm의 upper, lower보다 빠르다고 함. -> 주소로 반환

 

참고로 string은 string::npos, 

algorith, 헤더는 아래 처럼 작성하고, 똑같이 주소값으로 리턴된다.

lower_bound(arr.begin(), arr.end(), 6)

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

vector<int> univ(500000);
set<int> location;
int N, Q;
int dh = 0;

void transfer(int n) {
	if (location.find(n) != location.end()) {
		location.erase(n);
	}
	else {
		location.insert(n);
	}
}

void move(int n) {
	dh = (dh + n) % N;
}

int find() {
	if (location.empty())
		return -1;
	auto ans = location.lower_bound(dh);
	if (ans != location.end()) {
		return *ans - dh;
	}
	return N - dh + *location.begin();
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> Q;
	for (int i = 0; i < N; i++) {
		cin >> univ[i];
		if (univ[i])
			location.insert(i);
	}

	for (int q = 0; q < Q; q++) {
		int query, num;
		cin >> query;
		switch (query) {
			case 1: {
				cin >> num;
				transfer(num - 1);
				break;
				}
			case 2: {
				cin >> num;
				move(num);
				break;
			}
			case 3: {
				int ans = find();
				cout << ans <<'\n';
				break;
			}
		}
	}

}