BOJ 13701 중복 제거

이 문제는 N개의 정수가 주어지면, 이들 중 중복되는 것을 제거하고 주어진 순서대로 출력하는 문제인데, N은 최대 500만이고, 주어지는 정수의 크기는 최대 2^25 - 1 이다.
일단 바로 먼저 떠올리는 것이 boolean배열로 체크하는 것인데, 정수의 크기가 너무 커서 어림도 없다. 그렇다면 500만개니까 map을 쓰면 어떨까? map이 메모리를 얼마나 차지 하는지는 모르지만, 그냥 int형 배열만써도 500만개면 메모리 제한이 8MB를 초과할 것이다.

이거 참.. 그냥 int형 배열이라도 쓸 수 있으면 sorting이라고 해서 해볼텐데..(다행히 시간제한은 5초) 어떻게 해야할지 고민이다. 혹시 map으로 되는건가?
스택 오버플로우 맵 메모리 사용량 관련 사이트를 보니 int자료가 들어간 map을 쓰면 int형 배열보다 메모리를 더 많이 쓴다는 것을 알 수 있다.

맞은 사람 목록을 보니 코드가 매우 짧다... 그래서 혹시나해서 map을 썼는데 역시나 메모리 초과.

질문 게시판을 보니 https://www.acmicpc.net/board/view/10692


오.. 그래서 위의 힌트에 따라 좀 더 생각해 보기로 했다....
일단 int 형은 4byte.. boolean형도 1byte인데, 1bit면.. bit연산을 이용해야 하나...
확실히 이 숫자가 존재하는지 아닌지만 판단하면 되므로 0 or 1만 있으면 될 것 같긴한데, 어떻게 그런 자료구조를 써야할지...
일단 3000만 비트를 사용한다고 하면 대략 4MB가 든다. 오..

http://www.cplusplus.com/reference/bitset/bitset/ 을 보니 bitset의 각 요소는 1bit만 차지하고, 그래서 char보다 8배 작다고 나와있다.
사용법도  http://www.cplusplus.com/reference/bitset/bitset/operator[]/ 을 보면 배열과 비슷해 보인다...그리고 처음에는 0으로 초기화가 돼있어 보인다.

한 번 구현해 봐야겠다.
AC를 받고 다른 분들의 코드를 봤는데...bitset이 없어도 가능하다...!!! 와...!!

int형 배열은 32 bit, char형 배열은 8bit...
int형 배열을 쓴다고 할 때, 만약 어떤 수 num이 들어오면, num은 arr[num/32]의 num%32번째 비트에 기록해두면 되는 것이다!!! 아 이런 방법이.. 분명 처음 보는 방법은 아니지만.. 멋지다. 아름답다.

char형 배열을 쓴다면 num/8번째 배열의 수의 num%8번째 비트가 num에 해당하는 비트!

아 그리고 혹시 맨 끝의 비트 하나는 부호를 가리키는 비트 아니냐..니까 unsigned로 해야되지 않나 생각할 수 있는데 전혀 상관없는 것이 signed이든 unsigned이든 배열안에 저장되는(표현되는) int(또는 char)값만 달라지는 것이지 결국 비트를 사용하는 것은 똑같다.

정말 놀라운 방법이다. 구현해 봐야겠다.
AC를 받았다. 좋은 문제였다.