[프로그래머스 level3 징검다리 건너기] 이분탐색 활용하기

해결해야하는 문제는 다음과 같았다.

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

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

 

정확성만을 고려한 아이디어는 다음과 같다.

정확성만을 고려하여,, 해결한 코드는 다음과 같다.

def solution(stones, k):
    person = 0
    while True :
        temp = 0
        for i in range(len(stones)):
            if stones[i]==0 :
                temp += 1
                if temp >= k:
                    return person
            else :
                stones[i]-=1
                temp = 0
        person += 1

    return answer

 

 

 

하지만 이는 효율성 테스트를 통과하지 못한다!

효율성 테스트를 위해, 질문하기를 보며 힌트를 얻은 결과 이분탐색을 활용하라는 힌트를 얻을 수 있었다.

따라서 사람 수를 기준으로 이분탐색을 시작하도록 하였다.

 

 

이러한 아이디어를 통해 작성한 코드는 다음과 같다.

def possible(n,stones,k):
    stones = list(stones)
    if max(stones) < n:
        return False
    temp = 0
    for i in range(len(stones)):
        stones[i] -= n
        if stones[i]<0 :
            temp += 1
            if temp>=k :
                return False
        else :
            temp = 0
    return True

def solution(stones,k):
    left = 0
    right = 200000001
    mid = (left+right)//2
    max_stone = max(stones)
    while left< right :
        mid = (left+right)//2
        if left == mid or right==mid:
            break
        if possible(mid,stones,k) :
            left = mid
        else :
            right = mid
    return mid

 

다행히 효율성테스트도 통과할 수 있었다 !

효율성 테스트를 통과하지 못하는 경우, 해시 테이블 사용 , 2차원행렬->1차원의 긴 배열로 생각, 이분탐색 등의 방법들을 생각해보고 문제에 맞게 풀어내는게 중요할 것 같다!!