[LC] 668. Kth Smallest Number in Multiplication Table

<668. Kth Smallest Number in Multiplication Table> (#98)

Approach

O(m * n)이 아닌 방법으로 접근하기 위해서는 binary search를 적용해야 한다.

condition 함수 enough(num)은 num 이하인 값이 k개 이상 있는지 여부를 반환하도록 설계한다.

이렇게 하면 enough(num)를 만족하는 minimum num 값을 찾으면 된다.

def enough(num):
  cnt = 0
  # row 별로 확인
  for r in range(1, m + 1):
      # 현재 row의 모든 원소가 num 이하인 값이라면 최대 개수인 n(= row 내 모든 원소 개수),
      # 현재 row의 원소 중 일부가 num 이하인 값이라면 num // r 까지만!
      le = min(n, num // r)

      # le == 0이라면 early stop
      if le == 0:
          break

      # 현재 row에서 찾은 num 이하인 값 개수 업데이트
      cnt += le

  return cnt >= k

혹은 더 간단하게 다음과 같이 작성할 수 있다.

def enough(num):
  return sum(min(n, num // r) for r in range(1, m + 1)) >= k

search range는 [1, m * n]이며, 경계 축소 로직을 enough(num) 시 (minimum num을 찾기 위해) left를 더 확인하는 형태로 작성할 수 있다.

lo, hi = 1, m * n

while lo < hi:
  mid = lo + (hi - lo) // 2
  if enough(mid):
      hi = mid    # look for left
  else:
      lo = mid + 1    # exclude mid

return lo

[!caution] k-th 원소를 찾는 문제의 경우, condition 함수를 어떻게 설계해야 하고, 이를 만족하는 값 중 어떤 값을 찾아야 하는지를 잘 생각해야 한다.

Complexity

Time: O(m * log(m * n))
- [1, m * n]에서 binary search
- binary search의 각 iteration -> O(m)
Space: O(1)

seungriyou / algorithm-study

[LC] 668. Kth Smallest Number in Multiplication Table #99

Approach

Complexity