[CF 1154E] Two Teams

[CF 1154E] Two Teams - 1800

문제 설명 : 

1~n범위의 숫자가 고유하게 딱 한 개씩 주어진다. 매 시행마다 가장 큰 숫자를 찾아서 그 수와 그 수의 양 끝 k개의 숫자는 같은 team이 된다. team으로 묶인 숫자는 삭제한다. 이 시행을 모든 숫자가 team에 소속될 때까지 반복한다.

풀이 : 

그냥 naive하게 생각해봤을 때는 문제 설명 그대로 매 시행마다 가장 큰 수를 찾아서 양 끝의 k개를 지우면 될 것이다. 지운 숫자는 -1로 마킹해놓아서 이미 선택되었다고 표시해놓으면 된다. 하지만 이렇게 할 경우, 지워진 숫자가 연속되서 계속 나타날 수도 있으므로 최악의 경우 시간복잡도가 O(N^2)이 될 수도 있다. 따라서 나는 수를 지울 때의 연산을 좀 더 효율적으로 할 방법을 찾아야 한다. 

이때 사용할 방법이 바로 set을 사용하는 것이다. set에 지워지지 않은 숫자를 저장해놓을 것이다. 그래서 맨 처음에는 set에 1~n까지의 수를 모두 집어넣고, 숫자를 지워나갈 때마다 set에서도 해당 수를 지워나가는 방식이다. 이 방식의 경우는 시간복잡도가 O(NlogN)이 될 것이다.

주의할 점 : 

set에서 숫자를 삭제할 때 연산이 까다롭다. set의 iterator가 어떤 수를 가리키고 있는 상태에서 그 수를 삭제시키는 상황이 일어날 수 있다. 그러면 해당 iterator는 삭제된 수를 가리키고 있는 상황이므로 불안정한 상태이다. 삭제시킨 다음에 다음 혹은 이전 iterator에 접근해야 하는 상황이라면 여기서 에러가 날 수 있다. 이를 방지하기 위해서는 수를 삭제하기 이전에 미리 next 혹은 prev iterator를 미리 저장해놓은 다음 삭제를 진행해야 안전하게 iterator값을 얻을 수 있다(밑의 코드에서 pit,nit변수가 그 역할을 수행한다).

배울 점 : 

iterator 활용의 정점에 이른 문제가 아닐까 싶다. set에서 원소를 삭제할 때 iterator값을 미리 받아와야 안전하게 할 수 있다는 점을 배웠다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
priority_queue<int,vector<int>,greater<int>> mpq;
const int SPACE=0,NL=1;  string exm;
inline void showAll(vector<int> &v,int sep){ //0=space,1="\n"
    for(int &here:v) printf("%d%c",here,(sep)?'\n':' '); }
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
inline vector<int> int_seperation(int N,int d=10){
    vector<int> v; while(N){v.push_back(N%d); N/=d;}
    reverse(v.begin(),v.end()); return v; }
/*********************Contest Template***********************/
const int SIZE= 200009;
 
int arr[SIZE],ans[SIZE];
map<int,int> pos;
set<int> unused;
 
int main(){
    int n,k ;scanf("%d %d",&n,&k);
 
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&arr[i]);
        pos[arr[i]]=i;
        unused.insert(i);
    }
 
    int turn=1;
 
    while(!unused.empty()){
        int cur_val=pos.rbegin()->first,cur_pos=pos.rbegin()->second;
        pos.erase(cur_val);
        auto it=unused.find(cur_pos);
        auto pit=it,nit=it;
 
        int cnt=0,flag=0;
        if(it==unused.begin()) flag=1;
        else it=prev(it);
 
        for(; cnt<k && !flag ; cnt++,it=pit){
            if(it==unused.begin()) flag=1;
            ans[*it]=turn;
            pit=prev(it);
            unused.erase(it);
            pos.erase(arr[*it]);
        }
 
        cnt=0,flag=0;
        it=unused.find(cur_pos);
 
        if(next(it)==unused.end()) flag=1;
        else it=next(it);
 
        for( ; cnt<k && !flag ; cnt++,it=nit){
            if(it==unused.end()) break;
            ans[*it]=turn;
            nit=next(it);
            unused.erase(it);
            pos.erase(arr[*it]);
        }
 
        ans[cur_pos]=turn;
        unused.erase(cur_pos);
 
        turn^=3;
    }
 
    for(int i=1 ; i<=n ; i++){
        printf("%d",ans[i]);
    }
    return 0;
}