[BOJ] 13701 중복 제거

13701번: 중복 제거

문제

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

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

입력

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

12 1 449 12 555 1201 912 555 19372

출력

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

12 1 449 555 1201 912 19372

---

문제를 읽으면서 메모리 제한은 8MB, 입력은 500만 이하라는 것을 보고 문제가 범상치 않음을 느꼈다. 비록 내가 비트 집합 분류에서 문제를 고르긴 했지만 누가 봐도 비트 마스킹을 해야 할 것 같이 생겼다.

 

지금까진 비트마스킹을 하기 위해서 int형 변수를 사용했었다. int는 4byte이고 1byte가 8bit이므로 int는 32개의 bit를 가지고 있다. 입력되는 A는 최대가 2^25이니까 int가 2^20개만 있으면 된다. 이때 배열의 인덱스는 입력된 숫자를 32로 나눈 값이고 각 엔트리에서 비트의 위치는 32로 나눈 나머지를 사용하면 된다. 이때 32는 2^5니까 shift랑 AND 연산을 사용해서 값을 계산했다. 

 

나는 880ms 정도 걸렸는데 이걸 80ms대에서 해결한 사람도 있었다. 그 사람은 도대체 어떻게 시간을 그렇게 줄였는지 궁금해서 코드를 보고 싶었는데 그 사람 것은 못 보고 2등 코드를 볼 수 있었다. 코드를 봤더니 시스템 콜을 사용해서 코드를 작성했다. 아니 시스템콜까지...? 나는 바로 도망갔다.

 

후기)

비트 연산에 조금 더 익숙해진 것 같다.

세상에 최적화 방법은 정말 많다.