[백준] [이분탐색] K번째 수 : 1300 Python

이분 탐색 문제이다. 이 문제는 문제 설명 자체도 간단하지만 더 간략히 정리하자면, N*N크기의 이차원 배열에서 각 값은 row*col의 값을 가질 때(최소 인덱스를 1로 둠) T번째 수의 값을 구하는 것이다.

결국 T번째 수의 값을 이진탐색으로 찾아낼 수 있는 가를 구하는 문제이다.
역시 중간값 검증을 하여, 지금 탐색하고 있는 수가 몇 번째 수인지 찾아내는 것이 문제를 푸는 포인트인 것 같다.

1	2	3
2	4	6
3	6	9

N이 3인 이차원 배열은 이렇게 되고, 마치 구구단과 비슷한 모양이 된다. 이 배열에서 6은 몇번째로 큰 수인지 확인하기 위해서는 어떻게 해야 할까?

1행에서 6보다 작은 수는 3개, 2행에서 6보다 작은 수 역시 3개, 3행에서 6보다 작은 수는 2개로 총 8번째로 큰 수이다.
물론, 6이 두 개 있으므로 7번째로 큰 수이면서, 8번째로 큰 수이지만 어쨌든 우리가 원하는 수가 이 배열에서는 min(N, 기준수//i) 임을 알 수 있다.

이것을 활용하여 이분 탐색의 중앙값 검증을 진행한다면 우리가 원하는 수가 몇 번째 수인지 확인할 수 있을 것이다.

이런 방식으로 현재 내가 정한 기준값(middle) 보다 작거나 같은 수들이 앞에 몇 개 있는지 확인할 수 있다. 여기서 앞에 수들이 문제에서 원하는 수보다 많다면 middle을 정답 변수에 기록해놓고(위에 경우처럼 같은 수가 여러 개 있을 경우가 있기 때문) right 값을 줄이며 이분 탐색을 진행할 것이고, 그렇지 않다면 left값을 증가 시킬 것이다.

그 코드는 이렇게 된다.

이분탐색을 풀수록 정말 중앙값 검증하는 것이 어렵다는 것을 느끼고 있다. 

사실 중앙값을 검증하는 구현 실력을 늘리면 가장 좋겠지만, 적어도 어떤 문제를 읽었을 때, 이거 이분 탐색 문제이구나 하는 경지만 되었으면 한다.

문제 출처 : 백준 https://www.acmicpc.net/problem/1300

1300번: K번째 수