[Beakjoon] 23326 홍익 투어리스

바킹독 문제집을 천천히 따라가며 다시 풀어보기 시작했다.
이분 탐색 트리 파트에 있는 문제이다. set, map 자료구조가 이분탐색 트리 구조로 돼있다는 것을 처음 알았다. 또 어떤식으로 작동하는지도 대강 파악할 수 있었는데 꽤 흥미로웠다.

문제 링크

BOJ 223326 : 홍익 투어리스트

문제

풀이

현재위치에서 시계방향으로 이동할 때 가장 가까운 명소와의 거리를 계산해야한다.
명소는 최대 500000번째까지 존재한다. 조금 효율적인 방식을 생각해봐야한다는 것을 알 수 있고, 이분탐색을 이용해야겠다고 생각했다.

set을 이용하면 내부 값이 정렬상태를 유지한다. 또 erase와 insert작업도 O(logN) 안에 수행할 수 있다.

명소의 위치를 set자료구조 안에 정렬된 상태로 유지한다.
현재 위치에 대한 값을 계속해서 업데이트 해주다가, 거리 계산이 필요한 경우 이분탐색을 진행한다.

시계방향이라는 힌트가 주어졌으므로 자신의 위치보다 크거나 같은 위치에 존재하는 명소를 찾는다. 여기서 명소는 원형배치이므로 자신의 위치보다 오른쪽에 있는 명소가 없는 경우, 처음 등장하는 명소와의 거리를 계산해 출력해줘야한다.

코드1(insert, erase)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

#define endl "\n"

using namespace std;

int N, Q;
set<int> S;

void Solve() {
    cin>>N>>Q;

    int n, idx, now=1;
    long long x;
    for(int i=1; i<=N; i++){
        cin>>n;
        if(n==1) S.insert(i);
    }
    
    for(int i=0; i<Q; i++){
        cin>>n;
        
        if(n==1){
            cin>>idx;
            if(!S.erase(idx)) S.insert(idx);
        }
        else if(n==2){
            cin>>x;
            now+=(x%N); now%=N; if(now==0) now=N;
        }
        else{
            if(S.empty()) {
                cout<<-1<<endl;
                continue;
            }

            auto result = S.insert(now);         
            if(!result.second) cout<<0<<endl;
            else{
                if(next(result.first) == S.end()) cout<<N-now + *S.begin() <<endl;
                else cout<<*next(result.first) - now<<endl;
                
                S.erase(now);
            } 

        }
    }

}


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

    return 0;
}

코드2(lower_bound 사용)

주의할 점은 set library에 존재하는 lower_bound 함수를 사용해야 시간초과가 나지 않는다.

질문하기에 있는 답변이다.

std::lower_bound의 경우, set처럼 random access가 안 되는 iterator에 대해 O(lgN) 대신 O(N)의 시간복잡도를 가진다고 합니다.
반면 std::set::lower_bound는 set 내부의 트리 구조를 이용하여 구현이 되었기에 O(lgN)의 시간복잡도를 가질 수 있다고 합니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

#define endl "\n"

using namespace std;

int N, Q;
set<int> S;

void Solve() {
    cin>>N>>Q;

    int n, idx, x, now=1;
    
    for(int i=1; i<=N; i++){
        cin>>n;
        if(n==1) S.insert(i);
    }

    for(int i=0; i<Q; i++){
        cin>>n;
        if(n==1){
            cin>>idx;
            if(!S.erase(idx)) S.insert(idx);
        }
        else if(n==2){
            cin>>x;
            now+=(x%N); now%=N; if(now==0) now=N;
        }
        else{
            if(S.empty()) {
                cout<<-1<<endl;
                continue;
            }

            auto to = S.lower_bound(now);
            if(to == S.end()) cout<<N-now + *S.begin()<<endl;
            else cout<<*to - now<<endl;
        }
    }

}


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

    return 0;
}