이분 탐색 - 징검다리 건너기(카카오)

이번 문제는, 이분탐색 방법을 사용하는 카카오 인턴십 기출문제입니다

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

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

문제를 살펴보면, 두가지가 가능합니다.

 

문제의 제한조건을 살펴보면,

 

[제한사항]

• 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
• stones 배열의 크기는 1 이상 200,000 이하입니다.
• stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
• k는 1 이상 stones의 길이 이하인 자연수입니다.

 

stones의 크기가 최대 2000만 이기 때문에

 

반복문으로 한칸씩 까내려간다면 효율성 테스트 이전에 입구컷을 당합니다.

 

 

 

이번 문제는, 이분탐색 방법을 이용합니다.

https://teus-kiwiee.tistory.com/6?category=913862 

Binary Search

 

근데 저도 처음에 의문이 든건

"이분탐색은 정렬된 List에서 원하는 값을 찾는 방법"

인데, 이걸 어떻게 쓰는거지? 였습니다.

 

정답은 0~2000만 의 값을 가지고, 이분탐색으로 값을 뽑은다음 해당 값이 징검다리 건너기가 가능한가? 였습니다.

1. 0(left)~2000만(right) 사이의 중간값((0+20000000)//2)의 값을 선출

2. 해당 값만큼 나니즈 친구들이 건넜을 경우의 List를 검토

3. 건널수 있는가? -> 아직 원하는 값을 못찾았 으므로, 중간값+1~2000만 사이로 범위를 좁힘

   건널수 없는가? -> 원하는 값이 최소를 보장할 수 없으므로, 0~중간값-1 사의로 범위를 좁힘

 

이렇게 반복하다보면, left와 right의 값이 left<=right에서 left>right로 반전이 일어납니다.

 

이때 left가 정답이 되게 됩니다.

 

이유를 생각해보면, 건널수 있을 때는 left가 증가하고, 건널 수 없을때는 right가 감소합니다.

 

그렇다면, left<=right에서 left>right로 반전이 일어나는 경우는

1. left가 증가해서 left가 right보다 커짐(이분탐색 과정에서 right는 못건너는게 확인되어있음)

2. right가 감소해서 right가 left보다 작아짐(이분탐색 과정에서 left는 건널 수 있는 상태)

두가지 Case 모두 커지기 전 left일때는 건널 수 있고 left+1일 때 더이상 건너지 못하게 됩니다.

(저도 이부분이 좀 햇갈렸습니다)

 

 

Python으로 작성한 정답입니다 :)

import copy
def solution(stones, k):
    answer = 0    
    #left와 right의 위치를 처음에 결정
    left = 0
    right = max(stones)    
    while True:        
        #중간위치를 선정
        pivot = (left+right)//2        
        stones_copy = copy.deepcopy(stones)
        #중간 위치값일 때 징검다리를 건널 수 있는지 확인할
        #List를 생성
        stones_copy = [i-pivot for i in stones_copy]                
        #징검다리가 건널 수 없으면 +1씩 증가시키고
        #건널수 있으면 0으로 초기화
        empty_count = 0
        val = False
        for i in stones_copy:
            if i <=0:
                empty_count +=1
            else:
                empty_count = 0
            if empty_count >=k:                
                #건널수 있었는지, 없었는지를 저장
                val = True
                break     
        #건널수 있었으면 이분의 왼쪽을 탐색
        if val:
            right = pivot-1
        #건널수 없었으면 이분의 오른쪽을 탐색
        else:
            left = pivot+1                  
        if left>right:
            return left
            break