[프로그래머스/Python] Level 3_징검다리 건너기

📌문제 유형

2019 카카오 개발자 겨울 인턴십

 

📌문제

프로그래머스

 

📌나의 문제풀이

- 정확성 모두 통과, 효율성 0

def solution(stones, k):
    answer = 0
    
    while True:
        flag = 0
        tmp = 0
        
        # 1씩만 제거
        for i in range(len(stones)):
            if stones[i] > 0:
                stones[i] -= 1
            else:
                if tmp == 0:
                    before = i
                    tmp += 1
                else:
                    if i - 1 == before:
                        tmp += 1
                    else:
                        tmp = 1
                        
                if tmp == k:
                    flag = 1
                    break
                        
                before = i
            
                    
        if flag == 0:
            answer += 1
        else:
            break
    
    return answer

 

📌다른사람의 문제풀이

- 이진탐색 이용한 풀이

[프로그래머스] 징검다리 건너기(Python)

def solution(stones, k):
    left = 1
    right = 200000000
    while left <= right:
        temp = stones.copy()
        mid = (left + right) // 2
        cnt = 0
        for t in temp:
            if t - mid <= 0:
                cnt += 1
            else:
                cnt = 0
            if cnt >= k:
                break
        if cnt >= k:
            right = mid - 1
        else:
            left = mid + 1
        
    return left

 

📌리뷰

- 이분탐색 코드

[알고리즘 / Python] 이분 탐색 / 이진 탐색 (Binary Search)