백준 g3 23326 홍익 투어리스트 c++

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

23326번: 홍익 투어리스트

 

문제

홍익대학교에는 1~N개의 원형 구역으로 나뉘어져있다.

N개의 구역 중 명소인 곳이 1, 아닌 곳이 0으로 주어진다.

도현이의 위치는 1에서 시작한다.

 

Q개의 쿼리가 주어진다.

• 1 i : i번 구역이 명소면 명소에서 삭제, 명소가 아니면 명소로 추가
• 2 x : 도현이가 시계방향으로 x칸 이동한다
• 3 : 도현이가 시계방향으로 이동할 때 명소로 가려면 최소 몇 칸을 움직여야 하는지 출력

 

풀이

 

쿼리 3에서 시계방향으로 몇 칸 움직일지를 구해야하는데, 그냥 단순 배열로 구하면 최대 5*10^5 * 쿼리 개수 10^5개로 시간 초과가 날 수 있다. 명소인 장소들만 따로 저장해놓는 게 더 유리하다.

 

명소 리스트에 추가/삭제가 빈번하고, 도현이의 위치에서 가장 가까운 명소를 구할 수 있는 lower_bound가 있는 set 자료구조를 선택했다. 

 

수도 코드

set<int> sights; // 명소들이 몇 번 구역에 위치해 있는지

if: 1 i
	if 이미 i번 구역이 명소면
    	sights에서 i번 삭제
    else i번 구역이 명소가 아니면
    	sights에 i번 추가
else if: 2 x
	도현이의 위치 = (도현이의 위치 + x) % N;
    if 도현이의위치 == 0
    	도현이의 위치 = N
else if: 3
	if sights.empty()
    	-1 출력
    else
    	lw = sights.lower_bound(도현이의위치)
        // 도현이의 위치에서 시계방향으로 가장 가까운 명소 위치
        
        if (lw == sights.end()) // 끝까지 없으면 == 명소가 도현이보다 이전에 존재하면
        	(N-도현 위치) + lw 위치 출력
        else
        	lw - 도현위치 출력

2번 쿼리에서, 구획이 1번부터 시작하므로 그냥 0 ~ N-1에 하는 것처럼 %N한 후에 만약 0이면 N으로 값 수정하면 된다.

3번 쿼리에서, 

lw == sights.end()면 시계방향으로 도현이의 위치~N번 구역까지 명소가 없다는 뜻이다. 

그렇지만 sights.empty()는 아니므로(else) 1번 구역 ~ 도현이의위치에 명소가 있다는 뜻이다.

 

도현이의 위치 ~ N번 구역 + 1번 구역 ~ 명소의 위치 를 더해주면 값이 나온다.

 

전체 코드

/*boj g3 23326 홍익 투어리스트*/
#include <iostream>
#include <set>
#define MAXN
using namespace std;

int N, Q;
set<int> sights;

void print() {
    cout << "=========\n";
    for (auto i : sights) {
        cout << i << " ";
    }
    cout << "\n";
}
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int loc = 1;
    cin >> N >> Q;
    for (int i = 1; i <= N; i++) {
        int x;
        cin >> x;
        if (x == 0)
            continue;
        else
            sights.insert(i);
    }

    while (Q--) {
        int comm;
        cin >> comm;
        if (comm == 1) {
            int i;
            cin >> i;

            auto it = sights.find(i);
            if (it == sights.end()) {
                sights.insert(i);
            } else {
                sights.erase(it);
            }
        } else if (comm == 2) {
            int x;
            cin >> x;
            loc = (loc + x) % N;
            if (loc == 0) loc = N;
        } else if (comm == 3) {
            if (sights.empty()) {
                cout << -1 << "\n";
            } else {
                auto lw = sights.lower_bound(loc);

                if (lw == sights.end()) {
                    auto it = sights.begin();
                    cout << *sights.begin() + (N - loc) << "\n";
                } else {
                    cout << *lw - loc << "\n";
                }
            }
        }
    }
}