BOJ 13701 중복 제거 (비트마스킹, 비트 집합)

백준 BOJ 13701번 : 중복 제거

Solved.ac 난이도 : Gold III

알고리즘 분류 : 비트마스킹, 비트 집합

 

이 문제는 조건이 중요하기 때문에 정확히 적어두겠습니다. (비트마스킹을 반드시 이용해야만 풀 수 있는 문제이기 때문)

 

N개의 정수가 순서대로 입력될 때, 중복되어 나오는 수를 제외하고 출력하는 문제입니다.

이 때 N ≤ 500만이며, 입력되는 각 정수 A_i < 2^25입니다.

그리고 가장 강력한 조건은 메모리 제한인데, 이 문제에서는 메모리 제한이 8MB밖에 되지 않습니다.

 

 

 

따라서 저장 공간을 최대한으로 아끼기 위해 비트를 이용해 데이터를 저장하는 방식을 사용합니다.

각 A_i는 2^25 미만의 크기를 가지지만 용량을 위와 같이 계산해보면 int 배열은 최대 2^21칸 미만으로 사용 가능하므로, 우선은 2^20칸의 배열을 사용하고 나머지 2^5 비트에 대한 정보는 각 int의 비트에 저장할 수 있도록 합니다. (int는 32bit이므로 데이터 저장 가능)

 

예를 들어 A_i가 이진수로 101..001 10011이라면 (..001까지가 19자리)

arr[101..001(2)]의 int에 2^(10011(2)) = 2^19에 해당하는, 즉 뒤에서부터 19번째 bit를 1로 바꾸어주어 해당 값이 들어왔음을 저장하는 것입니다.

이제 다음에 이와 동일한 수가 들어왔다면 해당 비트가 이미 1로 켜져있을 것이므로 중복임을 알 수 있고 출력을 skip해주면 됩니다.

 

위에 대한 구현은 다음과 같이 할 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;

int arr[1<<20] = {};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N;

    while(cin >> N) {
        int q = N / (1 << 5);
        int r = N % (1 << 5);

        if(!(arr[q] & (1 << r))) {
            cout << N << " ";

            arr[q] += (1 << r);
        }
    }
}