[13701] 중복 제거

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

메모리 제한 8MB

n의 범위는 0<= n < 2^25

8MB는 약 2의 23승이므로

n의 범위만큼 배열을 만들 수 없습니다.

해쉬로 해결해보려했으나 N의 개수가 500만이여서 전부 저장할 수 없었습니다.

이 문제는 비트마스크로 해결할 수 있습니다.

핵심은 int가 32비트라는 점입니다.

int가 32비트이므로 비트를 32개 사용할 수 있는 것입니다.

n의 범위가 2^25이지만 몫을 배열의 인덱스로 사용하고 나머지를 해당 인덱스의 값에 비트로 저장하면 표현이 가능해집니다.

배열[ 입력받은 N / 2^5 ] = (N % 2^5) << 1

로 저장을 합니다.

그리고 존재하는지 검사를 할 때는 엔드 연산을 통해서 하면 되겠지요?

아래는 풀 코드입니다.

#include <cstdio>
 
int exist[(1 << 25) / 32];
int main() {
    int n;
 
    while (~scanf("%d", &n)) {
        int v = n / 32;
        int m = 1 << (n % 32);
 
        if (!(exist[v] & m)) {
            exist[v] += m;
            printf("%d ", n);
        }
    }
 
    return 0;
}