[CF 1208B] Uniqueness (좌표압축)

[CF 1208B] Uniqueness - 1500

 

문제 설명 : 

배열 a가 주어지고 나는 최대 1번의 연산을 통해 구간 [l,r]에 해당하는 범위의 원소를 제거할 수 있다. 이 결과로 남아있는 배열 a에 존재하는 모든 원소는 고유하게 만들어야 한다. 내가 제거할 구간의 길이가 최소가 되도록 하여라.

 

풀이 : 

두 가지 방법으로 풀 수 있다. 하나는 좌표압축과 이분탐색을 이용해서 모든 구간의 경우의 수(N^2)을 다 돌면서 구간의 lower bound를 찾는 방법이 있다. 좌표압축을 통해 수의 범위가 매우 커서 배열의 인덱스로 활용할 수가 없더라도 O(1)만에 바로 접근할 수 있는 방법이다. 자세한 설명은 아래에 한다. 

다른 한 방법은 투포인터를 이용한 방법이다. 배열에서 어느 구간을 삭제한다는 의미는 곧 배열의 prefix와 suffix만 남는다는 의미이다. 그래서 prefix를 먼저 고정시켜놓고, suffix의 길이가 얼마나 더 길어질 수 있는지 set(혹은 map)을 이용해서 값이 unique할 때까지 범위를 줄여나가는 방식이다. 

 

주의할 점 : 

처음에 이 문제를 풀 때는 좌표압축을 안하고 set을 이용해서 값의 uniqueness를 판단하려다가 O(N^2 log^2N)이 되어서 시간이 터졌다. set을 사용하지 않고 좌표압축을 하면은 O(logN)을 O(1)로 줄일 수 있다.

 

배운 점 : 

좌표압축은 원소의 값이 매우 커서 배열의 인덱스로 직접 사용할 수 없을 때 사용할 수 있는 테크닉이다. 이 문제의 경우 n의 최대 2000이지만 값은 최대 10억이다. 예를 들어서 원소가 {1,2,100,1억}이 있다고 해보자. 값 1억은 직접 배열의 인덱스로 넣을 수 없다. 따라서 나는 원소들을 크기순으로 정렬한 뒤에 해당 원소가 전체에서 몇 번째로 작은지를 새로운 인덱스로 매길 것이다. 그러기 위해서 원본 배열을 다른 컨테이너에 복제를 해 놓은 다음에, 오름차순으로 정렬한 뒤에 unique연산을 통해 중복을 제거해준다. 그런 다음 배열의 첫 번째 원소부터 차례로 보면서 해당 원소가 몇 번째로 작은지 lower bound연산을 통해서 계산해보면 된다. 총 드는 cost는 O(NlogN)이다.그렇게 하면{1(0),2(1),100(2),1억(3)} (괄호 안의 숫자가 좌표압축 후의 새로운 인덱스) 가 될 것이다. 

 

코드 : 

 

1. 좌표압축을 사용한 풀이

const int SIZE= 2009;

int arr[SIZE];
vector<int> comp;

int main(){
    int n;  scanf("%d",&n);

    for(int i=1 ; i<=n ; i++){
        scanf("%d",&arr[i]);
        comp.push_back(arr[i]);
    }    

    sort(comp.begin(),comp.end());
    comp.erase(unique(comp.begin(),comp.end()),comp.end());

    for(int i=1 ; i<=n ; i++){
        arr[i]=lower_bound(comp.begin(),comp.end(),arr[i])-comp.begin();
    }

    int l=-1,r=n+1;

     while(l+1<r){
        int mid=(l+r)/2;
        int poss=1;

        for(int i=1 ; i+mid-1<=n ; i++){
            int cnt[SIZE]={0};
            poss=1;
            for(int j=1 ; j<=n ; j++){
                if(j>=i && j<i+mid) continue;

                if(cnt[arr[j]]>=1) {
                    poss=0;
                    break;
                }
                else cnt[arr[j]]=1;
            }

            if(poss) break;
        }

        if(poss) r=mid;
        else l=mid; 
    }
    printf("%d\n",r);
    return 0;
}

 

좌표압축 부분

sort(comp.begin(),comp.end());
    comp.erase(unique(comp.begin(),comp.end()),comp.end());

    for(int i=1 ; i<=n ; i++){
        arr[i]=lower_bound(comp.begin(),comp.end(),arr[i])-comp.begin();
    }

 

 

2. 투포인터를 사용한 풀이

const int SIZE= 2009;

int arr[SIZE];

int main(){
    int n;  scanf("%d",&n);

    for(int i=1 ; i<=n ; i++){
        scanf("%d",&arr[i]);
    }

    int ans=1<<20;
    for(int i=1 ; i<=n ; i++){
        map<int,int> mii;
        int st=0,end=n+1;

        for(int j=1 ; j<i ; j++){
            if(mii[arr[j]]>0){
                break;
            }
            mii[arr[j]]++;
            st=j;
        }

        for(int j=n ; j>=i ;j--){
            if(mii[arr[j]]>0){
                break;
            }
            mii[arr[j]]++;
            end=j;
        }
        ans=min(ans,end-st-1);
    }
    printf("%d\n",ans);

    return 0;
}