문제

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

---

입력

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

---

출력

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

---

풀이

제한조건

• 5초, 8MB
• 0 ≤ Ai < 225 = 33554432

접근방법

비트마스킹

메모리 제한이 아주 인상적인 문제이다.
수의 범위가 매우 크기때문에, 조금 다르게 접근해야 한다.
문제를 보면 가장 먼저 드는 생각은 아래 2가지 이다.

1. 적당한 배열을 만들어 사용하기.
2. Set을 이용하여 풀이하기.

하지만, 저 숫자들을 하나 하나 담기에는 메모리 제한이 너무 빡빡하다.

(옛날 영화라 본 적 없음)

바로 비트마스킹을 통해서 해결해보자.
int가 몇 바이트 인지 생각해보자.

int는 4바이트. 즉 32비트이다.
이게 무슨 의미인가..

앞에서 1 또는 2번 방식을 사용할 경우 하나의 숫자는 4바이트를 모두 사용한다..!
하지만, bit 단위로 생각해본다면 int형 변수 하나가 무려 32개의 숫자를 커버할 수 있다.

bit로 표현된 수가 실제 어떤 값을 의미하는지는 중요하지 않다.
단지, n번째 의 bit가 1이라면, n번째에 해당하는 숫자가 입력되어 있다는 사실이 중요하다

A & (1 << B) == 1
-> B번째 비트가 켜져 있는가?

A | (1 << B) == 1
-> B번째 비트를 1로 변경..!

그럼 수의 범위가 2^25 이고, 2^5 =32 이므로, 대략 2^20승 정도 크기의 int형 배열만 있다면,
모든 수를 우리는 확인할 수 있다.

전체 과정

1. 전체 숫자를 나타낼 수 있는 배열을 만들자.
2. 비트 연산 &, | 을 통해 등장한 수 인지 확인하고, 기록한다.

번외

Java를 비롯한 인터프리터 언어에 대한 메모리 보너스가 너무 많아, 단순 Set으로도 통과된다고 한다.
C, C++에서는 보너스 없이, 8MB이므로 Set으로는 불가능하다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int[] bitset = new int[1 << 20 + 1];
		StringBuilder sb = new StringBuilder();
		String[] inputs = in.readLine().split(" ");
		for (String s : inputs) {
			int value = stoi(s);
			int idx = value / 32;
			int pos = value % 32;
			int bit = 1 << pos;
			if ((bitset[idx] & bit) == 0) {
				bitset[idx] = bitset[idx] | bit;
				sb.append(value).append(" ");
			}
		}
		System.out.println(sb);
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}