징검다리 건너기 (binarySearch)

2019 카카오 개발자 겨울 인턴쉽 "징검다리 건너기"를 정말 힘들게 풀었다.

 

처음에 탐색해야 할 범위가 200,000개가 넘어가는데 감이 안 잡혀서 일단 생각나는 대로 작성했다. 

 

처음 작성한 코드:

import sys; sys.setrecursionlimit(100000)
result = 0
def solution(stones, k):
    stop = 0
    while stop != k:
        stop=0
        for start in range(0,k):
            if not stones[start]:
                stop+=1
                continue
            cross(start,stones,k)
    return result

def cross(now,stones,k):
    global result
    stones[now] -= 1
    for plus in range(1,k+2):
        if plus == k+1:
            return
        if now+plus >= len(stones):
            result+=1
            return
        if stones[now+plus]:
            return cross(now+plus,stones,k)

 

한 명씩 건너면서 재귀를 통해서 돌의 숫자를 1씩 빼다가 k만큼 점프해도 넘어가지 못하는 경우가 발생하면 계속 1씩 더해왔던 전역 변수인 result(인원 숫자)를 반환하게 했다.

 

결과는 당연하게도 정확성 테스트는 통과했지만, 효율성에서 시간 초과가 떴다.

 

순차 탐색으로 구현했기에 한 최악의 경우 시간 복잡도가 n*n에 가까워지기 때문이다. (n은 디딤돌의 개수)

 

이진탐색을 써야할 것 같은데 평소에 라이브러리에 중독되어서 이진탐색을 bisect로 밖에 사용하지 않아서 도통 그림이 그려지지 않다가 

오랜 고민 끝에 떠오른 생각이 

   

    1. 건너가는 인원의 범위를 이진탐색으로 줄여가면서 탐색한다. 

    2. 돌의 값을 굳이 1씩 빼지 말고 지금 건너는 사람의 번호와 비교를 해서 못넘어가는 연속된 돌의 개수를 구해서 그게 만약 k와 같아지면          False를 반환한다. (다 넘어가면 True)

 

def solution(stones, k):
    global stone,K
    stone,K = stones,k
    if k == 1:
        return min(stones)
    start = 1
    end = max(stones)
    while(start < end -1):
        mid = (start+end)//2
        if cross(mid):
            start = mid
        else:
            end = mid
    return start

def cross(mid):
    global stone,K
    now = 0
    for rock in stone:
        if (rock < mid):
            now+=1
        else:
            now=0
        if(now>=K):
            return False
    return True

 

결국 정확성과 효율성 모두 통과했다.

 

시간복잡도는 n*n에서 mlogn로 줄어들었다.(m은 디딤돌에 적힌 숫자의 최댓값) 

 

 

이진탐색 코드

def binarySearch(target,start,end,data):
    if start > end:
        return

    mid = (start+end)//2

    if data[mid] == target:
        return mid
    elif data[mid] > target:
        end = mid - 1
    else:
        start = mid + 1
        
    return binarySearch(target,start,end,data)