유형: 이분탐색, 파라메트릭 서치
풀이방식: (풀이를 참고해)파라메트릭 서치를 이용해 풀 수 있었다.
[알고리즘 도출] 먼저 B배열과 K의 관계를 정의하면 좀 더 이해하기 수월하다.
B배열은 오름차순으로 정렬된 배열이므로, B[K] = x일때의 의미는
x보다 작거나 같은 원소의 개수가 최소 K개 존재한다는 의미이다.
따라서 x의 값을 이용해 파라메트릭 서치를 진행하면 된다.
그렇다면 x보다 작거나 같은 값을 어떻게 구할 수 있을까?
각 배열 요소의 값은 i * j이므로 각 행의 값의 배수들이 하나의 행을 이루고 있으므로
특정 수보다 작거나 같은 값은 num / 행을 1 ~ n행 까지 진행하며 count하면 된다.
다만 최대 n개의 요소가 한 행에서 나올 수 있는 최대의 개수이므로 Math.min(num / 행, n)으로 값을 더한다.
x = 5
n = 4
4 + 2 + 1 + 1
[Lower_bound? Upper_bound?]
| k | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| B[k] | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 4 | 6 | 6 | 8 | 8 | 9 | 12 | 12 | 16 |
k = 8, N = 4일 경우에 lower, upper중 어떤 방식으로 탐색해야 할까?
위의 표에서 x값이 4인 경우는 K = 6, 7, 8일 경우에 존재한다.
mid값을 구하면서 만약 mid = 5라면, 5보다 작거나 같은 값은 총 8개가된다.
[Upper_Bound]
upper bound라면 k == 구한 값일때 low값을 mid로 올려버리므로 결국 mid값은 6이 반환이 될 것이다. 따라서 -1을 뺀 값을 출력해도 기대값인 4가 아니라 5가 출력된다.
[Lower_Bound]
반면에 lower bound라면 위와 같은 상황에서 high값을 줄여가며 5보다 작은 값이 나타나는 최초의 인덱스인 6으로 결정되고 종료하므로 기대값인 4를 출력할 수 있다.
여기서 헷갈리지 말아야 할 것은 특정 K값이 있을때 B[K]의 값을 구해야 하긴 하지만, 그와 동일한 여러값이 있다면 그 중에 아무거나 결정해도 답이라는 사실이다. 따라서 확실하게 해당 B[k]를 가리키는 인덱스를 이용하면 되므로 lower bound를 이용한다.