문제 링크

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

사용 언어

C++14

소스

#include <cstdio>
  
int A[1048576] = {0, };
  
int main()
{
	int value;
	while(~scanf("%d", &value)){
		int* pt = A+value/32;
		int adj = 1 << (value % 32);
  		
		if(!(*pt & adj)){
			*pt |= adj;
			printf("%d ", value);
		}
	}
}

논리

논리는 굉장히 간단하다.

입력을 받은 후, 과거에 입력을 받은 값이면 아무 동작도 하지 않고,

과거에 입력을 받지 않은 값이면 즉시 출력하면 된다.

컴퓨팅적 문제

해당 문제를 bool exist[2²⁵]배열을 사용하여 해결 할 수 있을까?

bool은 1byte이므로 exist[2²⁵]는 2²⁵byte. 즉 32MB의 메모리를 사용하게 된다.

문제에서 제한한 메모리는 8MB이므로 bool배열을 이용하여 해결할 수 없다.

따라서 이 문제는 비트마스킹 기법을 이용해 해결해야 한다.

비트마스킹 기법을 이용하면 하나의 숫자를 체크하기 위해서 1bit가 필요하다.

따라서 2²⁵개의 중복을 체크하기 위해서는 2²⁵bit = 2²²byte = 2²MB = 4MB가 필요하다.

int변수 하나는 4byte이므로 크기가 2²⁰인 int배열을 선언하면 충분하다.