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

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

코딩테스트 연습 - 징검다리 건너기

 

문제유형 : 이분탐색

 

문제풀이 : 

• 이 문제를 보고 이분탐색이라고 판단해야 하는이유
  • 우선 범위가 2억이므로 매우크다 -> 이분탐색을 떠올린다!
  • 어떤 조건을 만족하는 인원수의 최대값을 구해야한다 -> 최적화문제 -> 파라메트릭서치를 이용한다. (어떤 조건에 부합하는 가능한 최대, 혹은 최소 등과같은 문제)
  • 여기서는 k가 주어질때 이 k의 조건을 만족하는 인원수의 최대이므로 인원수를 기준으로 이분탐색을 진행한다.
• mid명이 징검다리를 건넌다고 할때 가능한가? 에 대한 가설을 검증
  • mid명이 징검다리를 건널때 돌의 상태를 계속 체크하는데 앞에서부터 가다가 연속된 0이 k만큼 최초로 나온경우, 현재 mid명수의 사람은 건널수 없음을 의미하므로 left = mid-1를 통해 인원수를 줄여준다.
  • 만약 mid명이 징검다리를 건넜는데 연속된 0의 돌이 k미만이다? 현재의 인원수는 건너는게 가능하군! 인원수를 늘려줘본다.

 

정답코드

def solution(stones, k):
    left = 0
    n = len(stones)
    right = 200000000
    result = 0

    while left<=right:
        temp = stones.copy()
        # mid명일때 연속된 0 돌멩이가 k개 미만인가? 를 확인한다.
        mid = (left+right) // 2
        #print(mid)
        #print(left, right)

        count = 0
        for i in range(n):
            temp[i] -= mid # mid명이 건너갔을때의 현재돌 상황
            if temp[i] <= 0:
                count += 1
                if count >= k: #연속된 0 돌멩이가 k이상인경우 -> 현재의 mid명은 불가능하다.
                    break
            else:
                count=0
        # break로 포문을 빠져나온경우
        if count >= k:
            right = mid-1 # 인원을 줄여보자
        # for문이 끝나서 빠져나온경우 - 더 인원을 늘려보자
        else: # 현재의 인원을 저장하도록 한다.
            result = max(result, mid)
            left = mid+1

    return result+1