[백준]중복 제거(13701)

문제 링크 : [백준]중복 제거(13701)

13701번: 중복 제거

 

문제 설명

500만개 이하의 수가 주어집니다. 수는 0 ~ 2²⁵-1까지의 수로만 이루어집니다.

입력이 주어진 순서대로 중복을 제거하고 출력하세요.

단, 메모리는 8MB까지만 사용이 가능합니다.

입력

V_i(주어진 수, 0 <= V_i < 2²⁵)

12 1 449 12 555 1201 912 555 19372

 

출력

12 1 449 555 1201 912 19372

 

카테고리

#비트마스크

 

시간 복잡도 상한

O(NlogN)

 

해결 방법

1. used같은 사용여부 배열을 만들어서 풀면 쉬운 문제이나, 메모리 상한이 8MB이기 때문에 메모리가 부족합니다.
2. 주어진 메모리가 2²³이고, 수의 범위는 2²⁵-1까지 입니다. 비트로 따지면 25개의 비트가 필요합니다.
3. int는 4byte이고, 총 32개 비트(MSB는 부호비트니까 한개 빼면 31개)를 사용 할 수 있습니다.
4. 그러면 주어진 수의 왼쪽 20개비트를 배열의 인덱스로 사용하고, 나머지 오른쪽 비트를 배열에 저장합니다.
5. 그렇게 되면 왼쪽 20개비트가 이전에 사용되었는지는 확인 할 수 있으나, 나머지 오른쪽 5개 비트에 대해서 사용여부를 확인 할 수 없습니다.
6. 5개비트는 최대 31까지 나타낼 수 있고, 3.에서 얘기한 비트의 갯수와 동일합니다.
7. 즉, 오른쪽 다섯개 비트를 십진수로 나타낸 수만큼 1을 왼쪽으로 이동시켜 OR 연산을 통하여 사용 여부를 누적시켜 주면 됩니다.

시간복잡도

O(N)

코드

#include<cstdio>
int n,m,d[1000001],a,b,c;
int f(int a){
    if(a==d[a])return a;
    return d[a]=f(d[a]);
}
void u(int a,int b){
    d[f(a)]=f(b);
}
int main(){
    for(n=1;n<1000001;n++)d[n]=n;
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d%d",&a,&b,&c);
        if(a)printf("%s\n",f(b)==f(c)?"YES":"NO");
        else u(b,c);
    }
}