[백준] K번째 수 (1300번) - Python/알고리즘 설명

✅문제 - K번째 수 (1300번)

---

 

✅필요 알고리즘 개념 / 풀이 알고리즘

---

🔵이분탐색

◼ 소주병 뚜껑의 숫자 맞추기 처럼 Up Down 식으로 원하는 값을 찾아 가는 것이다.

◼ 정렬된 리스트에서만 사용이 가능하다.

 

🔵아이디어 - 이분탐색의 적용

◼ 숫자가 N^2개 존재하므로 1~N^2 번째 숫자까지 존재한다.

◼ k번째를 찾는 것이 아니라 1~N^2까지의 숫자를 선택해 해당 숫자보다 작은 숫자가 k개인 숫자를 찾는다.

 

🔵아이디어 - 특정 숫자보다 작은 숫자의 탐색

◼ 입력 받은 2차원 배열은 구구단의 성질을 띈다. 

◼ 이 성질을 이용하면 구구단 i단 에서 k보다 작은 숫자의 갯수는 k//i가 된다.

◼ 이 성질을 이용하여 1~N을 탐색하며 k보다 작은 숫자의 갯수를 센다.

 

✅코드

---

import sys

input = sys.stdin.readline

size = int(input().rstrip())
k = int(input().rstrip())

# left, right는 몇번째를 의미하는 것이 아니고 그냥 숫자를 의미한다,
left = 1
right = size**2
tmp = 0

while left <= right :
    mid = (left+right)//2

    # mid 보다 작은 숫자의 갯수를 count
    cnt = 0
    for i in range(1,size+1):
        # 구구단 i단에서 mid 보다 작은 숫자는 mid//i가 된다.
        # 이 때 숫자가 size 보다 커질 수는 없다.
        # 그러므로 min()을 이용해 최대값이 size가 되게 한다.
        cnt += min(mid//i,size)
    
    if cnt >= k:
        tmp = mid
        right = mid - 1
    else:
        left = mid + 1

print(tmp)

 

✅코드 설명

---

🔵 예제 입력

◼ 예제 입력의 경우 size = 3 이기 때문에 최소 1 ~ 최대 9 까지의 숫자가 있다. 그러므로 1~9의 숫자를 가지고 이분탐색을 진행한다.

 

🔵 예제 입력의 cnt 결과

for i in range(1,size+1):
    cnt += min(mid//i,size)

# 예제 입력의 2차원 리스트 테이블

1	2	3
2	4	6
3	6	9

각각의 숫자에 대하여 해당 숫자보다 작은 숫자의 개수(cnt)의 값은 아래와 같다.

숫자	1	2	3	4	5	6	7	8	9
cnt	1	3	5	6	6	8	8	8	9

❗❗❗여기가 중요하다.

예제에서 우리가 찾는 값은 7번째 숫자인데 cnt를 보면 7인 값이 없다.

같은 숫자가 여러개 일 수 있기 때문이다. 그러므로 우리는 cnt 값이 7이상인 값을 찾아야 한다.

그러면 cnt = 8 인 값이 총 3개 있는데 6, 7, 8 이다.

그렇다면 이 중에 우리 찾는 값은 무엇일까?

심지어 7과 8은 없는 수인데 이분 탐색을 통해 어떻게 찾아야 할까가 포인트이다.

❗❗❗그래서 중요한 것이 cnt 값이 처음 증가하는 부분인 6인 부분이다.

왜 6일 때 증가하는지 생각해보면 6이라는 숫자가 2차원 배열 리스트에 있기 때문에 cnt 값이 6에서 증가하는 것임을 알 수 있다.

7과 8도 cnt 값이 8이지만 cnt 값이 6일때와 비교해 증가하지 않았다.

이 말은 2차원 배열 안에 7과 8이 없다는 뜻이다.

👍그러므로 우리가 찾아야 하는 k번 째 숫자는 cnt 값이 k이상인 수 중에 가장 첫번째 값을 찾아야 한다 .!!!

🔵 이분 탐색 부분의 코드 설명

if cnt >= k:
    tmp = mid
    right = mid - 1
else:
    left = mid + 1

 

위의 설명에 의거해 cnt 값이 k이상인 값 중에 가장 작은 값을 찾아야 하므로 cnt >= k 일 때 right를 mid - 1로 옮겨가며 최솟값을 탐색한다.