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

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

프로그래머스

풀이

문제를 풀기 위한 가장 단순한 방법을 생각해 보면, 단순히 사람이 한 명씩 지나갈 때마다 돌의 밟을 수 있는 횟수를 1 줄이고, 더 이상 밟을 수 없는 돌이 연속적인지 체크하면서 더 이상 지나갈 수 없을 때까지 반복하였을 때 최댓값을 알아내는 방법이다. 하지만 이는 데이터의 수 때문에 불가능하다. 만약 20만 개의 돌을 2억 번까지 밟을 수 있다고 하면 반복문의 수가 20만 * 2억 = 40조 번으로, 파이썬의 1초에 계산할 수 있는 한계인 2천만을 아득히 넘어가게 된다. 그렇기에 n^2의 알고리즘인 단순 체크가 아닌 다른 방법을 생각해야한다.

생각을 바꿔서 특정 수의 사람이 주어진 돌들의 배열인 stones와 k개의 돌을 뛰어넘을 수 있는 상황에서 모두 건널 수 있는지 없는지를 사용해서 이진탐색으로 풀이한다. 만약 특정 수의 사람이 모두 강을 건널 수 있다면 사람의 수를 늘리고, 강을 건너는데 실패한다면 사람의 수를 줄여가며 가장 많은 사람이 건널 수 있는 경우를 찾아낸다.

def solution(stones, k):
    answer = 0
    
    low, high = 0, max(stones)
    
    while low <= high:
        mid = (low + high) // 2
        
        continous_rocks = 0 # 연속되는 돌의 수
        for stone in stones: # 전체 돌을 순회하면서
            if stone < mid: # 현재 위치의 돌이 mid명의 사람이 지나간 후 사라지는 돌이라면
                continous_rocks += 1 # 연속적인지 카운트
            else: # mid명의 사람이 지나간 후에도 남아있는 돌이라면
                continous_rocks = 0 # 연속된 돌의 수 초기화
                
            if continous_rocks >= k: # 연속된 사라진 돌의 수가 k 이상이라면 더 이상 체크할 필요가 없음
                break
        
        if continous_rocks >= k: # 연속된 돌의 수가 k 이상을 넘어서 mid명의 사람이 모두 건너지 못했다면
            high = mid - 1 # 건너는 사람의 수를 줄이기
        else: # mid명의 사람이 모두 건넜다면
            low = mid + 1 # 건너는 사람의 수를 늘리기
            answer = max(answer, mid) # 모든 사람이 건넜다면, answer에 최대값을 갱신
    return answer