[boj 1300] K번째 수 - 이분 탐색

문제 풀이 방식

이분 탐색

주의할 점

2차원 배열을 1차원 배열로 만드는 것이 가장 쉬운 방법이지만 이렇게 할 경우 배열의 크기가 너무 크므로 메모리 초과가 발생한다.

그러므로 특정 방식을 통해 이분 탐색으로 풀이했다.

만약 n = 3일 때, 2차원 배열은 아래와 같이 만들어진다.

1 2 3   - - - - - > Math.min( 4  / 1 , 3)  -> 3
2 4 6  - - - - - > Math.min( 4  / 2 , 3) -> 2
3 6 9  - - - - - > Math.min( 4 / 3 , 3)  ->  1

여기서 만약 7번째 수를 찾는다면 7번째 수보다 낮은 6개의 숫자를 찾으면 되는데, 이때 이분 탐색의 mid를 특정 숫자로 하여 아래와 같은 방법을 통해 찾아낼 수 있다.

위의 이차원 배열은 하나의 특징을 가지고 있는데 Math.min(특정 숫자 / 로우의 인덱스,  배열의 길이) -> Math.min( mid/ i, n)으로 특정 숫자보다 같거나 적은 크기의 개수를 구할 수 있다.

배열을 만드는 방식이 로우의 인덱스를 곱해서 만들기 때문에 가능한데, 위의 배열은 화살표로 표시한 것과 같이 특정한 숫자 4보다 같거나 작은 수의 개수를 각 3, 2, 1의 합인 총 6개로 카운트하여 나타낼 수 있다.

그렇다면 위의 이차원 배열을 일차원 배열로 변형해 오름차순으로 정렬하였을 때, 4는 6번째 수라는 것이다. 그렇다면 더 큰 수를 찾아야 하므로 left를 mid + 1로 해주고 새로운 mid를 정의하여 다시 탐색을 시작하면 된다.

소스코드