<이분탐색> 1300번 K번째 수 with 파이썬

 

문제

 세준이는 크기가 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]를 출력한다.

정답비율

 37.646%

알고리즘 분류

 #이분탐색

 

import sys
input = sys.stdin.readline

n = int(input())
k = int(input())

start, end = 1, n*n
while start <= end :
    mid = (start + end) // 2
    tmp = 0
    for i in range(1, n+1):
        tmp += min(n, mid//i)
    if tmp >= k :
        answer = mid
        end = mid - 1
    else :
        start = mid + 1
print(answer)

 

 - 문제에 나온대로 일차원 배열을 만들게 되면 이중반복문이 필요하고 시간복잡도가 O(n^2)이 된다. 문제에서 N은 10^5까지 주어진다고 했으므로 다른 방식을 찾아야한다.

 

 - 예시에 나온 3*3 을 살펴보자

 

  1  2  3

  2  4  6

  3  6  9

 

 - 위와 같은 배열이 만들어진다. k가 7로 주어졌는데, k번째 수라는 말은 이보다 작은 숫자가 k-1개가 있다는 말과 동일하다. 각 행을 살펴보면 출력으로 나온 6보다 작거나 같은 수가 3개, 3개, 2개 인 것을 알 수 있는데, 이는 min(6//행번호, n) 이다. 6보다 작거나 같은 수는 7보다 큰 8개라는 뜻이 된다. 6이 중복으로 나왔을 수 있기 때문에 어쨌든 6은 답이될 가능성이 있다. 만약 6이 아니라 5였다면 어땠을까. 총 5개로 답이 될 가능성이 없다. 즉 6이 답이다.

 

 - 위를 코드로 나타내면 이분탐색으로 나타내고, mid가 k보다 크거나 같으면 answer에 저장한다. 그리고 end를 줄여서 재탐색하며 반복한다. 만약 mid가 k보다 작으면 start를 올려서 재탐색한다.

 

 

---

 

 

참고

1300번: K번째 수