백준 13701 - 중복 제거 (C++)

문제

• 문제 링크

  
   BOJ 13701 - 중복 제거 
  

• 문제 요약

$N$개의 수가 주어진다.
이들 중 반복되는 수를 제외하고 남은 수들을 모두 출력해보자.

• 제한

TL : $5$ sec, ML : $8$ MB




$1 ≤ N ≤ 5,000,000$

$0 ≤ A_i < 2^{25}$

알고리즘 분류

• 비트 집합(bit set)
• 비트 마스킹(bitmask)

풀이

메모리 제한과, 주어지는 수의 개수 및 범위가 아주 인상적인 문제이다.

$⌈5,000,000 / 64⌉$ 개의 long long 변수를 가지고 mask를 해도 좋지만, C++ STL의 bitset을 이용하면 더욱 간단히 처리할 수 있다.
자세한 정보는 아래를 링크를 참고하자.

std::bitset

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    bitset <33554432> B;
    for (int i; cin >> i;)
        if (!B[i])
            B[i] = 1, cout << i << ' ';
}

comment

끝