[프로그래머스/Python파이썬] 징검다리 건너기

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/64062

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

 

 

문제 설명

건널 수 있는 사람의 수를 이진 탐색을 통해 구합니다. m명의 사람에 대해서 생각해보면, 한 번에 건너야 하는 디딤돌의 개수가 k개보다 크다면 m명의 사람은 건널 수 없습니다. 따라서 m보다 작은 값으로 다음 이진 탐색을 진행합니다. 만약 한 번에 건너야 하는 디딤돌의 개수가 k개 이하라면 m명의 사람이 다리를 건널 수 있으므로 m보다 큰 값으로 다음 이진 탐색을 진행합니다. 

 

1. 이진 탐색의 start, end를 초기화합니다. 
2. 한 번에 건너야 하는 디딤돌의 개수 중 최댓값을 구합니다. 
   - 디딤돌에 적힌 숫자가 건너야 하는 사람 수(m) 보다 작다면 마지막 사람은 해당 디딤돌을 밟지 못합니다. 
3. m명의 사람이 건널 수 없는 경우 end = m - 1로 설정합니다. 
   - 한 번에 k개 보다 더 많은 디딤돌을 건너야하는 경우입니다. 
4. m명의 사람이 건널 수 있는 경우 start = m + 1로 설정합니다. 
   - answer = max(answer, m)을 통해 가능한 m명 중에서 최댓값을 구합니다. 
5. start <= end동안 2~4번를 반복합니다. 

 

 

 

 

소스코드

def solution(stones, k):
    answer = 0
    start, end = min(stones), max(stones)
    # 이진 탐색
    while start <= end:
        m = (start + end) // 2
        # 한 번에 건너야 하는 디딤돌의 개수 중 최댓값
        n, max_jump = 1, 0
        for s in stones:
            if s - m >= 0: 
                max_jump = max(n, max_jump)
                n = 1
            else: # 디딤돌을 밟지 못하는 경우
                n += 1
        max_jump = max(n, max_jump)
        
        # m명의 사람이 건널 수 없는 경우
        if max_jump > k: 
            end = m - 1
        # m명의 사람이 건널 수 있는 경우
        else:
            start = m + 1
            answer = max(answer, m)

    return answer