K 번째수 - 파이썬 (이분탐색)

사이트 링크 : https://www.acmicpc.net/problem/1300 

 

문제는 아래와 같습니다.

문제

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력

• 첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.

출력

• B[k]를 출력한다.

문제 해결 포인트 

• 문제의 아이디어가 떠오르지 않아 정말 시간을 많이 사용한 문제였습니다. ㅋㅋ 
• 해당 문제에서 가장 중요한 포인트는 count_below 함수안에 count += min(number//row,n) 입니다

문제에서 n을 5라고 가정한뒤 이차원 배열을 만들면 아래 표와 같습니다 

찾아야 하는 값 mid 이 5라고 한다면 5보다 작거나 같은 집합 요소의 개소는 총 5+2+1+1+1 로 10입니다. 

이건 row 에서 각 값을 1 ~ n 까지 곱한것과 같으므로  이걸 mid 값으로 나눈다면 작거나 같은 값구할수 있습니다.

그렇다면 min(number/row,n) 에서 n 값과 비교를 한 이유는 최대 column 이 n 개 이기때문에 최대값으로 n값을 초과할수 없도록 

선언을 해두었습니다 (다른 블로그를 참고하였는데 정말 이러한 아이디어가 없다면 풀기가 힘든 문제인것 같습니다.)

그렇다면 mid 값의 count를 할수있는 최대 값을 얻을수 있고 그것을 기반으로 k값으로 이진 탐색을 하면 문제는 풀립니다. 

 

 

정답코드 

from sys import stdin

def count_below(number):
    count = 0
    for row in range(1, n+1):
        count += min((number) // row, n)
    return count


n = int(stdin.readline())
k = int(stdin.readline())

while left <= right:
    middle = (left + right) // 2
    if count_below(middle) >= k:
        right = middle - 1
    else:
        left = middle + 1
print(right)

 

해당 문제는 계속 리뷰를 해서 코드를 정교화 해보는것도 좋은것 같습니다.