[PG/Python] 징검다리 건너기

📌 문제

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

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

 

📌 문제 접근 방법

1. 처음엔 당연히 효율성에서 0점을 맞을 줄 알면서도 한 명씩 징검다리를 건너는 상황을 구현했다.
   역시 효율성을 통과 못하고 찾아봤더니 결국 이분탐색..!
2. 징검다리에 적힌 숫자의 최소와 최대를 시작과 끝으로 정하고 이분탐색으로 풀었다.
3. 근데 사실 아직 answer를 갱신하는 부분이 이해가 잘 안간다... if-else문에서 else문에 answer를 갱신하도록 했더니 테케 2개가 자꾸 틀려서 if문쪽으로 올려줬더니 성공했다..
   나중에 이분탐색을 다시 공부해봐야겠다..!

 

📌 코드

def solution(stones, k):
    answer = 0
    while True:
        jump = 0
        for i in range(len(stones)):
            if stones[i] == 0:
                jump += 1
                if jump >= k:
                    break
            else:
                jump = 0
                stones[i] -= 1
        
        if jump >= k:
            return answer
        else:
            answer += 1

-> 효율성 0점

 

def solution(stones, k):  
    min_people = min(stones)
    max_people = max(stones)
    
    answer = 0
    while min_people <= max_people:
        mid = (min_people + max_people) // 2
        array = [stone - mid for stone in stones] # mid명의 친구가 징검다리를 건넌 뒤 디딤돌에 적힌 숫자
        
        cnt = 0
        for a in array:
            if a <= 0:
                cnt += 1
                if cnt >= k:
                    break
            else:
                cnt = 0
        
        if cnt >= k:
            max_people = mid - 1
            answer = mid
        else:
            min_people = mid + 1
    
    return answer

-> 이분탐색, 통과