문제 출처

1. 문제설명

  • 자세한 설명은 문제 링크 참조
  • N개의 구역이 원형으로 배치된다.
    • N+1인 경우, 1번 구역으로 가게 된다는 뜻
  • 쿼리를 수행
    • 1, i : i가 명소가 아니라면 명소로, 명소라면 명소가 아니도록
    • 2, x : 현재 위치에서 시계방향으로 x만큼 이동
    • 3 : 명소에 도달하기 위해 시계 방향으로 몇 칸 움직여야 하는지
      • 명소가 없다면, -1


2. 알고리즘 설계

  • set을 이용해 풀이하였다.
  • 입력받을 때 명소인 곳만 set에 번호로 저장한다.
  • 1번 쿼리 : 명소 번호가 set에 존재하면 삭제하고, 그렇지 않은 경우 추가
  • 2번 쿼리 : % 연산자를 이용해 원형에도 OOM이 나지 않도록 구현
  • 3번 쿼리
    • set이 비어있다면, 명소가 없다는 뜻
    • 그렇지 않으면, set에 상한값을 찾는다.
      • 전체 길이에서 현재 위치를 빼주고(== 현재 위치에서 마지막 장소까지 이동거리),
      • 현재 지정된 가장 첫 명소의 번호를 더함(== 1번째 위치부터 몇 칸 앞으로 가야하는지).


3. 전체 코드

  • 변수는 편의상 재사용 하였다!
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

int n, p, l, m;
string opt;

int P[100005];
set<int> L[105];

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

    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> p >> l;
        P[p] = l;
        L[l].insert(p);
    }

    cin >> m;
    while(m--) {
        cin >> opt;

        if(opt == "recommend") {
            cin >> p;

            if(p == 1) {
                for(int i=100; i>=0; i--)
                    if(!L[i].empty()) {
                        cout << *prev(L[i].end()) << '\n';
                        break;
                    }
            }
            else {
                for(int i=0; i<=100; i++)
                    if(!L[i].empty()) {
                        cout << *L[i].begin() << '\n';
                        break;
                    }
            }
        }
        else if(opt == "add") {
            cin >> p >> l;
            P[p] = l;
            L[l].insert(p);
        }
        else {
            cin >> p;
            L[P[p]].erase(p);
        }
    }

    return 0;
}