[백준] 13701 중복 제거

BIT를 이용해 풀 수 있는 문제다

int 형은 4byte = 32bit 이므로 1bit에 숫자 하나를 표현한다고 치면 

32개의 숫자를 표현 가능하다

32 = 2^5 이고 숫자가 2^25 까지 들어오므로 2^20개의 int형이 있으면

모든 숫자를 표현 가능하다

그럼 이제 int로 32개의 숫자를 표현하는 방법에 대해 알아보자

이건 2차 배열에서 x,y를 숫자 하나로 표현하는 방식과 비슷하다

숫자 n을 표현할 때 n/32는 몇번째 숫자로 표현 하는지 의미하고

n%32 는 그 숫자에서 몇번째 비트로 표현 하는지 의미한다

만약 5라면 0번째 숫자 5번째 비트이므로

a[0]의 5번째 비트다 

있는지 확인하려면 a[0] &( 1<<5)를 해보면 알 수 있다!

소스코드

#include <iostream>
#include <bitset>
using namespace std;
int a[(1 << 20)],n;
int main() {
    while (scanf(" %d", &n) != -1) {
        int x = n / 32;
        int y = n % 32;
        if (!(a[x] & (1 << y))) {
            printf("%d ", n);
            a[x] |= (1 << y);
        }
    }
}

이 문제는 bitset으로도 풀이 가능

소스코드

#include <iostream>
#include <bitset>
using namespace std;
 
bitset<(1 << 25)> bt;
int s;
 
int main() {
    int num;
    
    while (scanf("%d",&num) != EOF) {
        if (!bt[num]) {
            bt[num] = 1;
            printf("%d ", num);
        }
    }
    return 0;
}