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

2019 카카오 개발자 겨울 인턴십 - 64062. 징검다리 건너기

Python 풀이

 

풀이

일단, 효율성을 측정하는 문제이기 때문에,

한 명이 징검다리를 건널 때 마다 모든 돌에 -1을 하고,

그 때마다 k보다 간격이 큰 징검다리가 있는 지 검사하는 방식은 통할 리가 없음.

def solution(stones, k):
    for i in range(1, 200000000):
        stones = list(map(lambda x: x-1, stones))
        cnt = 0
        for stone in stones:
            if stone < 1:
                cnt += 1
                if cnt == k:
                    return i
            else:
                cnt = 0

이런 식으로.

당연히 정확성만 통과, 효율성은 통과 하나도 못 함.

 

 

풀이 2

이것도 Union-Find로 풀릴만한 문제인가 싶어

Union-FInd로 풀어 봤으나..

도저히 효율성에 통과할 것 같지 않고 복잡해져 포기.

 

 

풀이 3

그렇다면 이분탐색(Binary Search)을 이용해 보는 것으로.

[프로그래머스] 43236. 징검다리 라는 비슷한 문제도 있다.

 

1 ~ 200,000,000 사이의 숫자 중에서, 건널 수 없게 되는 순간인 숫자(건널 수 있는 사람 수)를 이분탐색으로 구하는 것.

def solution(stones, k):
    def consecutive(A):
        cnt = 0
        for stone in stones:
            if stone <= A:
                cnt += 1
            else:
                cnt = 0
            # k를 넘으면 컷 (효율)
            if cnt >= k:
                return cnt
        return cnt


    high = 200000000
    low = 0
    answer = 0
    while low <= high:
        mid = int((high+low) / 2)
        num = consecutive(mid)

        if num >= k:
            high = mid - 1
        elif num < k:
            low = mid + 1
            
    return low