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

문제

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

프로그래머스

 

 

 

---

 

주요 아이디어

최대 몇 명까지 징검다리를 건널 수 있는지 return해야 하는 이분탐색 문제이다.

• "최대로 건널 수 있는 명 수"를 이분탐색 타깃으로 둔다
• 건널 수 있는지, 없는지를 판별
  • 건널 수 있으면 인원을 증가
  • 건널 수 없으면 인원을 감소

 

---

 

코드 구현 (Python 3)

 

def can_check(bridge, people, k):
    # 0 이하 구간이 연속되는 최대 횟수
    cnt = 0
    
    for stone in bridge:
        # 뛰어 넘을 수 없는 칸 : 남은 칸수 - 사람 수 음수면 못뛰어넘는 칸 +1
        if stone < people:
            cnt += 1
            if cnt >= k:
                return False
        else:
            cnt = 0
    
    return True       

def solution(stones, k):
    start, end = 0, max(stones)
    max_people = 0
    
    while start <= end:
        mid = (start + end) // 2
        # print('## people : ', mid)
        
        # 건널 수 있다는 뜻
        if can_check(stones.copy(), mid, k):
            max_people = max(max_people, mid) # 최대값 갱신
            start = mid + 1
            
        # 건널 수 없으면
        else:
            end = mid - 1
    
    return max_people

 

 

---

 

제출 결과