[알고리즘] 감추어진 자연수들을 정렬했을 때 가장 큰 Gap 찾기

조건

- 1~M 까지의 범위에서 N개의 자연수가 입력으로 감추어진다.

- M은 N에 비해 매우 크다.

 

이 자연수들을 정렬했을 때 가장 큰 Gap(즉, 인접한 두 자연수의 차이를 찾아라)

 

제공

Query(x,y)를 호출하면 x부터 y까지의 범위에서 입력 자연수들 중 가장 작은 값과, 가장 큰 값을 리턴한다.

 

만약 n=8, m=93

 

알고리즘 :

1. Qurey(1,M)을 호출하여 가장 작은 값과, 가장 큰 값을 알고 시작한다.

가장 작은 값 : T1, 가장 큰 값 : Tn

2. T1 + 1 ~ Tn - 1 구간을 (N-1)개로 균일하게 나누어 Query를 호출한다.

3. 각각 호출하여 알아낸 최소, 최대값을 이용하여 가장 큰 Gap을 찾는다. 호출하지 않은 정보들은 무시해도 된다.

 

이게 가능한 이유는, N-1개의 범위에 N-2개의 값이 있기 때문이다.

이 말은 결국, 한 범위는 빌 수 밖에 없다.

범위가 빈다는 것은 결국 Gap이 다른곳에 비해 크다는 것으로 판단하면 되고,

이와 같은 정보를 취합하여 결과를 도출해낼 수 있다.