프로그래머스 / 징검다리 건너기 / python

첫 시도 코드

def solution(stones, k):
    answer = 0
    idx = 0
    l = len(stones)
    
    while True:
        while idx < l and stones[idx] == 0:
            cnt -= 1
            idx += 1
            if cnt == 0:
                return answer
        if idx < l:
            stones[idx] -= 1
        idx += 1
        cnt = k
        if idx >= l:
            answer += 1
            idx = 0
        
    return answer

처음에는 위와 같이 완전탐색 방식으로 풀었었다.

결과는 효율성에서 0점이다. stones을 한 번씩 순회하면서 1씩 빼는 방법으로 하기에는 stones의 원소 최대 값이 너무 크다... 당연한 결과이다.

def solution(stones, k):
    answer = 0
    start, end = 0, max(stones)
    
    while start < end:
        mid = (start+end) // 2
        cnt = 0
        for i in range(len(stones)):
            if stones[i] - mid <= 0:
                cnt += 1
                if cnt == k:
                    break
            else:
                cnt = 0
        if cnt >= k:
            end = mid
        else:
            start = mid + 1
        
    return start

이분탐색으로 풀이
이 문제는 최소값을 찾는 문제이므로 이분탐색에서 lower case 문제이다.
이분탐색으로 풀이 결과

이분탐색으로 풀이 했음에 불구하고 효율성에서 3개의 케이스에 대서 시간초과가 나왔다......
다른 분들은 이분 탐색으로도 해결했던데.....

---

이분 탐색을 스스로 떠올리지 못했다.. 확실히 경험 부족이 느껴진다. 좀더 정진하자