[백준] 1300번 : K번째 수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1300번: K번째 수

 

1. 문제 설명

2. 풀이과정

 

해당 문제에서 K의 범위가 1~min(10^9, N^2)이므로 시간 복잡도가 N^2인 알고리즘을 사용할 수 없다.

해당 문제를 이진 탐색 알고리즘으로 해결하여 중앙값보다 작은 수의 개수를 세면서 범위를 절반씩 줄이는 방법으로 K번째 수를 구한다.

중앙값보다 작은 수의 개수가 K - 1개인 중앙값이 K번째 수가 되는 것이다.

 

2차원 리스트는 N행이 N의 배수로 구성되어 있으므로 2차원 리스트에서의 K번째 수는 K를 넘지 않는다.

이는 2차원 리스트의 1~K번째 안에 정답이 있다는 것을 의미한다.

이 점에 주목하여 이진 탐색의 초기 시작 인덱스를 1, 종료 인덱스를 K로 정하여 정답을 찾는다.

중앙값보다 작거나 같은 수의 개수는 중앙값을 N으로 나눈 값이다.

중앙값보다 작은 수의 개수가 K보다 작으면 시작 인덱스를 중앙값 + 1로, 중앙값보다 작은 수의 개수가 K보다 크거나 같으면 종료 인덱스를 중앙값 - 1로 변경하며 정답을 찾는다.

 

슈도코드

1. N(리스트의 크기) 입력받기
2. K(구하고자 하는 index) 입력받기
3. start(시작 인덱스 = 1)
4. end(종료 인덱스 = K)
5. answer(정답 = 0 초기화)
6. while (start <= end):
   1. middle(중간 인덱스 구하기 = 중앙값)
   2. count(중앙값보다 작은 수)
   3. for i는 1~N까지: count += 중앙값을 i로 나눈 값과 N 중 작은 값
   4. if (count < K): start = middle + 1
   5. else: end = middle - 1, answer = middle
7. 정답 출력

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())
K = int(sys.stdin.readline())

start = 1
end = K
answer = 0

while (start <= end):
    middle = int((start + end) / 2)
    count = 0
    for i in range(1, N + 1):
        count += min(int(middle / i), N)
    
    if (count < K):
        start = middle + 1
    else:
        end = middle - 1
        answer = middle

print(answer)