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

[문제]

디딤돌의 내구도와 한번에 건널 수 있는 디딤돌의 갯수가 주어졌을 때 최대 몇명이 건널 수 있는지 계산하는 문제 입니다. 

입출력 예시 : stones = [2, 4, 5, 3, 2, 1, 4, 2, 5, 1], k = 3

 

[풀이]

1. 아주 간단한 방법:

한명씩 건넌다고 치고 stones의 모든 원소값을 1씩 빼고 다시한번 0이하의 값이 연속되는지 확인합니다. 

하지만 이 방법은 2중 for문으로 n^2의 시간복잡도가 소요됩니다.  원소의 최대값은 2억이고,  배열의 크기의 최대값은 20만이므로 

n^2의 방법으로는 1초안에 풀이가 불가능합니다.  

 

2. 이진탐색법의 LogN의 시간복잡도를 활용

몇명이 건널 수 있는지가 문제이기때문에 몇명인지를 이진탐색으로 탐색해서 구해보면 빠르게 구할 수 있을거 같습니다.

가능한 최대로 건널 수 있는 사람의 수는 stones 원소의 최댓값입니다. (모든 디딤돌이 최댓값일 경우)

가능한 최소로 건널 수 있는 사람의 수는 stones 원소의 최솟값입니다. (모든 디딤돌이 최솟값일 경우) 

따라서 min_v(left) = min(stones), min_v(right) = min(stones) 로 정해줍니다.

그리고 중간값 (mid_v = min_v  + (min_v + max_v) // 2) 을 건널 수 있는 사람의 수로 생각하고

내구도가 0보다 떨어지는 디딤돌이 k개 보다 많은지 확인하고 많으면 max값을 줄여주고, 적으면 min값을 올려줘서 k값에 근접하도록 풀어준다.

 

[코드]

def solution(stones, k):

    min_v = min(stones)
    max_v = max(stones)
    while min_v <= max_v:
        mid_v = min_v + (max_v - min_v) // 2
        count = 0
        over = False
        for i in range(len(stones)):
            if stones[i] - mid_v <= 0:
                count += 1
                if count == k:
                    over = True
                    break
            else:
                count = 0
        if over:
            max_v = mid_v - 1
        else:
            min_v = mid_v + 1
    return min_v