[프로그래머스] 징검다리건너기 - python 파이썬

문제

 

 

 

이 문제를 보면 일단 엄청 큰 범위가 가장 중요하게 고려해줘야 하는 부분이다. 

 

건널 수 있는 사람수의 최댓 값은 모든 stone이 200,000,000인 경우이므로 200,000,000 이 된다.

 

이렇게 범위가 굉장히 큰 경우에는 일단 "이분 탐색"을 먼저 떠올려 주는게 좋다.

 

이분탐색을 이 문제에 적용하게 된다면 target은 정답이 되는 건널 수 있는 사람 수 가 되어야 한다.

 

 

더 자세한 부분은 작성한 코드를 바탕으로 설명하자면

 

 

def solution(stones, k):
    left = 1
    right = 200000000
    
    while(left<=right):
        tmp = stones.copy()
        mid = (left+right)//2
        
        cnt = 0
        for t in tmp:
            #못건너는 다리의 수
            if t - mid<= 0 :
                cnt += 1
            else:
                #연속하는 0의 개수만 세도록 처리
                cnt = 0
            #연속되는 못건너는 다리의 길이가 k를 넘으면 종료
            if cnt >= k:
                break
        #못건너는 다리의 길이가 k보다 길다는건 현재 인원이 건널 수 있는 최대 인원보다 크다는 것
        if cnt >= k :
            right = mid - 1
        if cnt < k:
            left = mid + 1
    return right

 

 

일단 최댓값이 되는 right는  말했듯이 200,000,000 이고 최소는 범위가 1 이상으로 주어졌기 때문에 left는 1이 된다.

 

그리고 다리를 못건너게 되는 경우는 0인 돌이 k이상 연속으로 올 때이다.

 

이때 연속된 돌의 개수를 세주기 위해 t-mid가 0이하가 아니면 연속된 돌의 개수를 세는 변수인 cnt를 0으로 리셋 해주면된다.

 

그리고 이렇게 계산한 cnt가 k 이상이라는 뜻은 현재 건너는 인원이 해당 다리에서 건널수 있는 최대인원을 넘어버렸기 때문에 k이상이 되는 것이므로 right를 줄여준다. ( 반대의 경우는 left를 키우기)

 

 

이분 탐색을 활용하는 법이 어려웠던 문제였던 것 같다. (ex: 연속되는 0의 개수 처리 등등)