10.7 빠뜨린 정수

문제 

음이 아닌 정수 40억 개로 이루어진 입력 파일이 있다. 이 파일에 '없는 정수'를 생성하는 알고리즘을 작성하라. 단, 메모리는 1GB만 사용할 수 있다. 

- 연관문제 

 메모리 제한이 10MB라면 어떻게 풀 수 있을까? 중복 되는 값은 없으며, 이번에는 정수가 10억 개만 있다고 가정하자. 

 

접근법

우선 40억개라는 수의 의미를 알아야 했다. 40억개는 즉 2의 32승이 조금 안되는 수이다. 

하지만 음이 아닌 정수라고 햇으니 2의 31개의 수가 40억개(2의 32승) 있다고 하니 중복되는 값이 있을 것이다.

제공된 메모리는 1GB => 2^30 *2^3 만큼의 비트를 사용할 수 있을 것이다. 따라서 2의 31 만큼의 수들을 모두 표현하기에 충분한 양이다. 

 

따라서 

1. 40억 비트의 크기인 비트벡터를 만든다. 

2. 이 비트벡터를 0으로 초기화한다. 

3. 파일의 모든 숫자를 읽어 나가면서 비트벡터의 해당 숫자의 인덱스의 비트를 1로 변경해준다.

4. 0번째 인덱스부터 순환하면서 없는 정수를 찾는다.

5. 0인 인덱스를 반환한다. 

 

- 연관문제 접근법

전체 데이터를 2번 읽으면 빠진 정수값이 무엇인지 알 수 있다.

전체 데이터를 특정 크기만큼 분할 한다음에 중복되어 있지 않기 때문에 그 분할된 범위안의 숫자가 몇개가 나왔는지 count한 다음에

그 범위 만큼만 비트벡터로 나오지 않은 값을 확인한다.

 

메모리가 10MB라는것은 거의 2^23 byte를 사용할 수 있다는 것이다. int는 4byte를 사용하기 때문에 최대 2^21개의 블럭을 만들 수 있다. 

블럭의 갯수 = 2^31 / 블럭의 크기  <= 2^21

따라서 블럭의 크기 >= 2^10 일 것이다.

 

그다음에 블럭이 만약 1000짜리 크기라면 999개가 나온 블럭만을 비트벡터로 설정하고 나오지 않은 수를 찾아내는 방식을 도입한다.

 

만약 메모리가 더더더 작아진다면

블럭의 갯수를 줄이고 (블럭의 크기를 키워서) 탐색한 후 1개 모자르게 나온 블럭만을 또 나누어서 탐색하며 여러번 반복해서 탐색하다가 비트벡터로 찾을 수 있을 양까지 범위가 적어지면 그때 나오지 않은 수를 찾아낼 수 있을 것이다.