문제 요약
디딤돌을 밟을 때마다 해당 디딤돌의 숫자가 1씩 감소한다.
숫자가 0인 디딤돌은 밟을 수 없으며, 친구는 최대 k칸까지 건너뛸 수 있다. 모든 친구는 한 명씩 순서대로 징검다리를 건넌다.
최대 몇 명의 친구가 건널 수 있는지 구해야 한다.
핵심 관찰
어떤 인원 x명이 건널 수 있다면, 그보다 적은 인원도 반드시 건널 수 있다.
반대로 x명이 건널 수 없다면, 그보다 많은 인원도 건널 수 없다.
통과 가능: 1명, 2명, ..., x명
통과 불가능: x + 1명, x + 2명, ...이처럼 정답을 기준으로 가능과 불가능이 나뉘는 단조성이 있으므로 이분 탐색을 사용할 수 있다.
x명이 건널 수 있는지 판정하기
x명이 디딤돌을 밟으려면, 숫자가 x보다 작은 디딤돌은 x번째 친구가 밟을 수 없다.
stone < x밟을 수 없는 디딤돌이 k개 연속으로 나타나면 친구는 그 구간을 넘어갈 수 없다.
친구는 최대 k칸까지 건너뛸 수 있으므로, 밟을 수 없는 디딤돌이 k개 연속이면 다음으로 밟을 수 있는 디딤돌까지의 거리가 k + 1칸 이상이 된다.
따라서 다음 조건이면 x명은 건널 수 없다.
숫자가 x보다 작은 디딤돌이 k개 연속 존재한다.이분 탐색 범위
건널 수 있는 친구 수는 최소 1명 이상이고, 어떤 디딤돌의 숫자 최댓값보다 많을 수 없다.
left = 1
right = max(stones)중간값 mid를 기준으로 mid명이 건널 수 있는지 판정한다.
- 통과 가능: 더 많은 인원이 가능한지 확인하기 위해
left = mid + 1 - 통과 불가능: 인원을 줄이기 위해
right = mid - 1
Python 코드
def solution(stones, k):
left = 1
right = max(stones)
answer = 0
while left <= right:
mid = (left + right) // 2
consecutive_unavailable = 0
can_cross = True
for stone in stones:
if stone < mid:
consecutive_unavailable += 1
if consecutive_unavailable >= k:
can_cross = False
break
else:
consecutive_unavailable = 0
if can_cross:
answer = mid
left = mid + 1
else:
right = mid - 1
return answer코드 설명
기준 인원 설정
mid = (left + right) // 2mid는 현재 통과 가능 여부를 확인할 친구 수다.
밟을 수 없는 디딤돌 확인
if stone < mid:
consecutive_unavailable += 1디딤돌의 숫자가 mid보다 작으면, mid번째 친구가 해당 디딤돌을 밟기 전에 숫자가 0이 된다.
따라서 이 디딤돌은 기준 인원의 친구가 사용할 수 없는 디딤돌이다.
연속 구간 검사
if consecutive_unavailable >= k:
can_cross = False
break사용할 수 없는 디딤돌이 k개 연속이면 최대 점프 거리로도 다음 디딤돌에 도달할 수 없다.
이 경우 더 확인할 필요 없이 현재 인원은 통과 불가능하다고 판단한다.
최대 인원 갱신
if can_cross:
answer = mid
left = mid + 1
else:
right = mid - 1통과 가능하면 현재 mid를 정답 후보로 저장하고 더 큰 값을 탐색한다.
통과 불가능하면 더 작은 인원 범위만 탐색한다.
정확성
기준 인원 x에 대해 숫자가 x보다 작은 디딤돌은 x번째 친구가 밟을 수 없다.
밟을 수 없는 디딤돌이 k개 미만으로 연속되면 친구는 그 디딤돌들을 한 번에 건너뛰어 다음 디딤돌을 밟을 수 있다. 반대로 k개 이상 연속되면 다음 사용 가능한 디딤돌까지의 거리가 최대 점프 거리보다 크므로 통과할 수 없다.
따라서 판정 함수는 x명이 건널 수 있는지 정확히 판단한다.
또한 어떤 인원이 통과 가능하면 더 적은 인원도 통과 가능하고, 어떤 인원이 통과 불가능하면 더 많은 인원도 통과 불가능하다. 이분 탐색은 이 단조성을 이용해 통과 가능한 인원 중 최댓값을 찾으므로 반환값은 정답이다.
시간 복잡도
디딤돌 개수를 N, 디딤돌 숫자의 최댓값을 M이라고 하자.
통과 가능 여부를 한 번 판단하는 데 최대 O(N)이 걸리고, 이분 탐색은 O(log M)번 수행된다.
O(N log M)N은 최대 200,000이고 M은 최대 200,000,000이므로 충분히 처리할 수 있다.
공간 복잡도
입력 배열 외에 연속 개수, 탐색 범위 등 상수 개수의 변수만 사용한다.
O(1)주의할 점
- 디딤돌 숫자가
mid와 같으면mid번째 친구는 해당 디딤돌을 밟을 수 있다. 따라서 조건은stone <= mid가 아니라stone < mid다. - 연속으로 사용할 수 없는 디딤돌의 개수가
k가 되는 순간 통과할 수 없다. - 모든 친구를 실제로 한 명씩 시뮬레이션하면 디딤돌 숫자 범위가 커서 시간 초과가 발생한다.
- 답은 최소 디딤돌 숫자가 아닐 수 있으므로 이분 탐색으로 정확한 최대 인원을 찾아야 한다.
정리
이 문제는 친구 수를 직접 시뮬레이션하지 않고, 특정 인원 수가 통과 가능한지를 판정하는 문제로 바꾸는 것이 핵심이다.
기준 인원보다 작은 디딤돌이 k개 연속인지 검사하고, 이 판정 결과에 이분 탐색을 적용하면 최대 통과 인원을 효율적으로 구할 수 있다.
