BOJ 12722(Mousetrap (Large))풀이

이미지를 누르면 문제로 이동합니다

문제를 간단하게 요약하면 처음부터 i를 증가하며 카운팅을 하는데 i번째 값이 i 라면 그 값을 지우고 카운팅을 1부터 다시 한다. 이렇게 계속 반복해서 값을 계속 지우는데 지워지는 값이 1부터 차례대로 지워지게 하는 크기가 K이 배열에서 n개의 인덱스가 주어지면 그 위치의 값을 출력하는 문제이다.

 

K=5 일 때 [1, 3, 2, 5, 4] 이렇게 배열을 만들면 차례로 값을 지울 수 있다. 

처음에는 i가 1이고 값도 1이므로 1을 지우고 3부터 다시 i=1을 시작해서 카운팅 해 나가면 2가 지워지고 계속 반복하게 되면 1, 2, 3, 4, 5 순서대로 지워지게 된다. 

 

여기서 한가지 알 수 있는 사실은 i 번째 값이 지워졌다면 다음 값은 i+(i+1) = 2i+1 위치에 있어야 한다. 그러므로 1부터 K까지 진행하면서 알맞은 위치에 값을 순서대로 넣어주면 끝이다. 하지만 이렇게 진행하다 보면 i가 K 보다 커지게 되기도 하고 이미 값이 넣어져 있는 곳도 있을 것이다. 잘 생각해보면 이미 값이 넣어져 있다는 것은 그 위치에 값은 이미 지워졌다고 볼 수 있다. 그러므로 그다음 위치에 값을 넣는 다면 위 조건을 충족하게 된다. 그다음 위치에도 값이 들어 있다면 계속 반복하면서 비어져 있는 위치에 값을 넣어주면 된다. 

만약 i가 k보다 커지가 된다면 처음부터 다시 세어주면 된다. 문제를 읽어보면 값들이 계속 회전한다는 것을 알 수 있다. 그렇기 때문에 i가 K보다 커지게 된다면 처음부터 다시 세어주면 되는 것이다.

 

이 과정은 세그를 이용하면 O(TKlogK) 안에 해결할 수 있다.

세그를 이용해서 비어져 있는 공간의 개수를 세고 자신이 다음에 넣어야 할 위치를 계산해서 그 위치에 값을 넣어준다. 이를 1부터 K까지 모두 반복한 다음 입력에 맞는 위치의 값을 출력해주면 된다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,k,a,b;
ll st[1000100];
ll ck[1000100];
ll ip[1000100];
ll B=1;
vector<ll>seg(4000000);
struct nd{
    ll left,right;
};
void sg(ll n,ll s,ll e){
    seg[n]=0;
    if(s==e)return;
    ll mid=(s+e)/2;
    sg(n*2,s,mid);
    sg(n*2+1,mid+1,e);
    return;
}
void up(ll n,ll s,ll e,ll idx){
    if(idx<s||idx>e)return;
    if(s==e){seg[n]=1;return;}
    ll mid=(s+e)/2;
    up(n*2,s,mid,idx);
    up(n*2+1,mid+1,e,idx);
    seg[n]=seg[n*2]+seg[n*2+1];
}
void sh(ll n,ll s,ll e,ll v,ll j){
    if(s==e){//==B
        B=s;
        if(ck[s]>0)st[s]=j;
        seg[n]=1;
        return;
    }
    ll mid=(s+e)/2;
    if((mid-s+1)-seg[n*2]<v){
        sh(n*2+1,mid+1,e,v-((mid-s+1)-seg[n*2]),j);
    }else{
        sh(n*2,s,mid,v,j);
    }
    seg[n]=seg[n*2]+seg[n*2+1];
}
ll sm(ll n,ll s,ll e,ll left,ll right){
    if(e<left||right<s)return 0;
    if(left<=s&&e<=right)return seg[n];
    ll mid=(s+e)/2;
    return sm(n*2,s,mid,left,right)+sm(n*2+1,mid+1,e,left,right);
}
nd ss(ll n,ll s,ll e,ll idx){
    if(s==e)return{seg[n],0};
    ll left=0,right=0,mid=(s+e)/2;
    if(idx<=mid){
        nd BB=ss(n*2,s,mid,idx);
        right=BB.right+seg[n*2+1];
        left=BB.left;
    }else{
        nd BB=ss(n*2+1,mid+1,e,idx);
        left=BB.left+seg[n*2];
        right=BB.right;
    }
    return{left,right};
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> t;
    ll A=0,C=0,D=0,Q=0;
    nd CX={0,0};
    fill(st,st+1000100,0);
    fill(ck,ck+1000100,0);
    for(int i=0;i<t;i++){
        cin >> k;
        cin >> a;
        for(int j=0;j<a;j++){
            cin >> b;
            ip[j]=b;
            ck[b]++;
        }
        sg(1,1,k);
        st[1]=1;
        up(1,1,k,1);
        A=0,B=1,C=0,D=0,Q=0;
        CX={0,0};
        for(int j=2;j<=k;j++){
            CX=ss(1,1,k,B);
            C=CX.right;
            if(j<=(k-(B+1)+1)-C){
                D=CX.left;
                Q=j+(B-D);
            }else{
                A=(j-((k-(B+1)+1)-C)-1)%(k-seg[1])+1;
                Q=A;
            }
            sh(1,1,k,Q,j);
        }
        cout << "Case #" << i+1 << ": ";
        for(int j=0;j<a;j++){
            cout << st[ip[j]] << ' ';
            ck[ip[j]]--;
            if(ck[ip[j]]==0)st[ip[j]]=0;
        }
        cout << "\n";
        
    }
}