[2016 홍익대학교 프로그래밍 경진대회] 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’을 출력한다.

 

 

int가 32비트이므로 int하나에는 32개의 비트체크를 할수 있다.

2^23은 32로 나누면 2^20개의 int가 있다면 비트 체크가 가능하다

따라서 2^20개의 int 배열을 만든다.

32로 나눈 몫을 배열의 인덱스, 그리고 나머지를 해당 인덱스에서 체크하는 비트로 생각하면

arr[x] & (1 << y) 가 있다면 해당 값이 비트 체크 된것이다.

따라서 비트 체크가 안되있다면 출력하고 그자리를 채우면 된다.

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<stack>
#include<set>
#include<map>
using namespace std;
int arr[(1 << 20)];
int n;
int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	
	
	while (scanf("%d",&n) != -1)
	{
		int x = n / 32;
		int y = n % 32;
		if (!(arr[x] & (1 << y)))
		{
			printf("%d ", n);
			arr[x] |= (1 << y);
		}
	}
}