K번째 수 ( 1300 번 )

1300번: K번째 수

 

---

🧠 알고리즘

• 이진 탐색 (Binary Search)

 

✔️ 동작 방식

• 문제 핵심 아이디어
  • NxN 배열 A[i][j] = i × j에서, B 배열은 이 모든 수를 오름차순으로 정렬한 결과이다.
  • 그러나 실제로 배열을 만들면 O(N²)이라 너무 느리므로,
    “어떤 수 mid 이하의 원소가 몇 개인지(count)”를 세는 방식으로 K번째 수를 찾는다.
• 이진 탐색으로 K번째 수를 찾기
  • 탐색 범위는 1부터 k까지 (K번째 수는 절대 K보다 클 수 없음).
  • 중간값 mid를 기준으로,
    각 행(i)마다 mid // i개의 값이 mid 이하이므로
    count = sum(min(mid // i, n) for i in range(1, n+1)) 로 계산한다.
  • count는 “mid 이하의 숫자가 몇 개인가”를 의미한다.
    • 만약 count >= k라면 → K번째 수는 mid보다 작거나 같다 → r = mid - 1
    • 그렇지 않으면 → K번째 수는 mid보다 크다 → l = mid + 1
  • 이렇게 탐색을 반복하면서 정답 후보를 answer = mid로 갱신한다.
• 종료 조건
  • l > r가 될 때 종료되며, answer에는 K번째 수가 저장되어 있다.

---

 

🧾 코드

import sys

def _main(n, k):
    """
    [
        [1, 2, 3],
        [2, 4, 6],
        [3, 6, 9]
    ]
    >> [1, 2, 2, 3, 3, 4, 6, 6, 9]
    k의 위치를 찾는것이 킥!!
    이분탐색 ㄱㄱ max 값은 k 초과 불가
    """
    l, r = 1, k
    while l <= r:
        mid = (l + r) // 2

        now_count = sum(min(mid // i, n) for i in range(1, n + 1))

        if now_count >= k:
            r = mid - 1
            answer = mid
        else:
            l = mid + 1
    
    return answer
        

n = int(sys.stdin.readline().rstrip())
k = int(sys.stdin.readline().rstrip())
print(_main(n, k))

---

 

⏱️ 시간 복잡도

while l <= r : 이진 탐색 ( 로그 시간 복잡도 )
	now_count = sum(min(mid // i, n) for i in range(1, n + 1)) : 현재 갯수 확인 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )