징검다리 건너기

https://school.programmers.co.kr/learn/courses/30/lessons/64062 (opens in a new tab)

해설

정확성 해설 : 친구들이 더 이상 징검다리를 건널 수 없을 때까지 시뮬레이션해본 후, 최대 몇 명이 건널 수 있는지 구해주면 됩니다.

효율성 해설 : 다양한 풀이가 있을 수 있으며, 다음과 같은 방법을 통해 효율성 풀이를 통과할 수 있습니다.

연속된 K개의 디딤돌에 적힌 숫자가 모두 0인 구간이 있으면 더 이상 징검다리를 건널 수 없으며, 이를 이용해 이분 탐색하면 문제를 해결할 수 있습니다. 먼저 M번째 친구가 징검다리를 건널 수 있는지 확인하기 위해 M – 1 번째 친구까지 징검다리를 건넌 상황을 구합니다. 이때, M – 1번째 친구까지는 K값에 관계없이 모두 징검다리를 건넜다고 가정합니다. 따라서, 징검다리에 적힌 숫자가 M보다 작다면 숫자가 0이 됐다고 표시해주면 됩니다. 이제 M번째 친구가 징검다리를 건널 수 있는지 확인하기 위해 징검다리에서 0이 연속으로 K개가 나오는 구간이 있는지 확인합니다.

0이 연속으로 K개가 나오는 구간이 있는 경우 : M번째 친구는 징검다리를 건널 수 없습니다.
또한, M번째 친구보다 뒤에 건너는 친구들은 모두 징검다리를 건널 수 없습니다.
따라서 찾아야 하는 답은 0 이상 M – 1 이하인 정수 중 하나입니다.
0이 연속으로 K개가 나오는 구간이 없는 경우 : M번째 친구는 징검다리를 건널 수 있습니다.
이 경우 첫 번째 ~ M – 1 번째 친구들은 모두 정상적으로 징검다리를 건널 수 있습니다.
따라서 찾아야 하는 답은 M 이상 MAX값 이하인 정수 중 하나입니다.

답이 될 수 있는 최솟값과 최댓값의 중간값으로 M값을 계속 변경해 주면 효율적으로 탐색 범위를 줄여나갈 수 있습니다. 위 풀이의 경우 시간 복잡도는 O(nlogm)이 되며, n은 디딤돌의 개수, m은 디딤돌에 적힌 숫자의 최댓값입니다. 이 외에 O(n) 풀이 방법도 있으니 한 번 고민해보세요.

문제 풀이

def solution(stones, k):
  answer = 0
  left, right = 1, max(stones)
  while left <= right:
    # ct에 들어가는 값은 stones와 mid의 값을 뺏을 때
    # 건너뛰어야 하는 돌의 개수를 카운팅하는 변수이다.
    ct = 0
    mid = (left + right) // 2
    for stone in stones:
      
      # 해당 돌을 건너 뛰어야 한다면 ct 값을 올린다.
      if (stone - mid) <= 0:
        ct += 1
      # 해당 돌을 건널 수 있다면 ct 값을 0으로 만든다.
      else:
        ct = 0
      # ct 값이 최대로 건너뛸 수 있는 개수 이상이 된다면 break로 멈춘다.
      if ct >= k:
        break
        
    # 건너뛴 횟수(ct값)이가 k 보다 작다면
    # left 값을 더 늘려서 더 큰 값을 찾는다.
    if ct < k:
      left = mid + 1
    # ct가 k 보다 크거나 같다면
    # right 값을 줄여서 재탐색한다.
    else:
      answer = mid
      right = mid - 1
 
  return answer