[C/C++] 백준 - 13701번 (중복제거) ; 비트마스킹/비트집합

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

13701번: 중복 제거

문제

문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때,

1. 0 ≤ Ai < 225 = 33554432, i=1,2,…,N.
2. 입력의 개수 N은 1 이상 500만 이하이다.

입력

첫째 줄에 A1, A2, ..., AN이 주어진다.

출력

B1, B2, ..., BN’을 출력한다.

---

바로 직전 글에 작성한 [비트마스크를 이용한 에라토스테네스의 체]와 비슷한 개념의 문제를 풀어보았다.

메모리 제한은 8MB로 작은 편이지만 n의 범위는 0<=n<2^25로 단순 배열로 문제를 해결할 수 없다.

따라서 비트마스크를 이용한 배열로 문제를 해결해야한다.

 

이 문제를 해결하기 위한 핵심은 입력으로 주어지는 수가 2의 25승보다 작으며 int가 32비트라는 점이다.

int가 32비트이므로 비트를 32개 사용하여 문제를 해결할 수 있다.

 

에라토스테네스의 체를 해결하는 과정처럼 몫을 배열의 인덱스로 사용하고 나머지를 해당 인덱스 값에 비트로 저장하면 된다.

 

int fullSet[(1 << 25) / 32];

 

위와 같이 배열을 선언하여 비트로 표현하기 위한 과정을 진행해준다.

이제는 전 게시글에서 진행한 것과 똑같이 구현해주면 된다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define Mod 1000000007
#define endl '\n'

using namespace std;

int fullSet[(1 << 25) / 32];

void solution(){
    while(1){
        int x;
        cin >> x;
        if(cin.eof() == true){
            break;
        }

        if(!(fullSet[(x / 32)] & (1 << (x % 32)))){
            fullSet[(x / 32)] += (1 << (x % 32));
            cout << x << " ";
        }
    }
}

int main(){
    fastio;
    solution();

    return 0;
}

 

전역변수로 fullSet 배열을 선언해주었기 때문에 내부에는 모두 0으로 초기화되어있다. 따라서, 처음 입력하는 수인지 이미 입력했던 수인지 확인하는 코드는 아래와 같이 내부에 이미 값이 존재하는지 확인해주면 된다.

 

if(!(fullSet[(x / 32)] & (1 << (x % 32)))){
    fullSet[(x / 32)] += (1 << (x % 32));
    cout << x << " ";
}

 

배열 내부에 아무런 수도 저장되어있지 않다면 처음 입력한 값으로 인식하고 출력과 동시에 값을 저장해주면 된다.