[PG] 징검다리

문제

Me

import heapq
def solution(stones, k):
    answer = 0
    noMore = False
    while not noMore:
        min_stone = 0
        temp = stones[:]
        heapq.heapify(temp)
        for i in range(len(temp)):
            if min_stone == 0 and temp[i]!=0:
                min_stone = temp[i]
                answer+=min_stone
                break
        if min_stone==0 : break
        zero_gap =0
        for i in range(len(stones)):
            if stones[i] != 0 :
                stones[i]-=min_stone
                zero_gap = 0
            else:
                zero_gap+=1
            if zero_gap>=k:
                noMore = True
                break
    return answer

• 가장 최솟값을 heap으로 찾아 감소 시키기
• 이 후 0의 연속된 것을 체크해 k개 이상이라면 더이상 건너지 못하므로 진전 안함

정답율도 1개, 이후 다 틀림 ^^..

답

1. 이분탐색

• 특정 값으로 감소시킨 후 0 연속이 k를 넘는지 안넘는지 체크
• https://leetcode.com/problems/sliding-window-maximum/solutions/237611/Simplest-O(n)-Python-Solution-with-Explanation/ 참고