[BOJ] 13701 중복제거 C++

https://www.acmicpc.net/problem/13701

13701번: 중복 제거

수들이 주어졌을 때, 중복한 수가 온다면 출력하지 않는 문제이다. 주어진 메모리가 8MB 밖에 되지 않으므로 비트마스킹으로 이용해야 한다. int형은 4byte 이므로 4*8=32bit이다. 따라서 32가지의 숫자를 저장할 수 있다. 최대 2^25의 수가 주어지기 때문에 2^25/32=2^20의 크기의 배열이 있다면 주어지는 모든 수를 저장 할 수 있다.

숫자 n이 주어지면 n/32의 배열 인덱스에 1<<n%32를 저장해 주면 된다.

 

코드

#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);
        }
    }
}