[프로그래머스][Level3] 징검다리 건너기 (파이썬)

---

문제출처

https://school.programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스

---

문제를 스스로 해결하였는가?  ->  O

 이분탐색 아이디어를 떠올리기까지 그리 오래 걸리지 않았다. 하지만 효율성 검사를 통과하기가 꽤나 까다로웠다. 초기에 작성한 실패코드와 성공코드를 같이 놓고 어떤 차이가 있었는지 비교하자.

---

사용된 알고리즘

• 이분탐색

---

실패 코드

def solution(stones, k):
    left, right = 0, max(stones)
    while left <= right:
        mid = (left+right)//2
        cnt, maxi = 0, 0
        for stone in stones+[mid]:
            if stone < mid:
                cnt += 1
            else:
                maxi = max(cnt, maxi)
                cnt = 0
            if maxi >= k:
                right = mid-1
                break
        if maxi < k:
            left = mid+1
    return right

 정확성 테스트에선 통과됐으나 효율성 13번에서 시간초과가 발생한 코드다. 반복문 내에서 max함수를 계속해서 사용했던게 문제였던 것 같다.

---

성공 코드

def solution(stones, k):
    left, right = 0, max(stones)
    while left <= right:
        mid = (left+right)//2
        cnt, maxi,flag = 0, 0, True
        for stone in stones:
            if stone < mid:
                cnt += 1
            else:
                cnt = 0
            if cnt >= k:
                right = mid-1
                flag = False
                break
        if flag:
            left = mid+1
    return right

 flag 변수를 사용해 반복문마다 불필요한 max 함수 사용을 제거했더니 통과됐다.