[프로그래머스] 징검다리 건너기 / Python / 2019 카카오 겨울 인턴십

https://programmers.co.kr/learn/courses/30/lessons/64062?language=python3

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

---

---

Solution

def niniz_jump(stones, k, mid):
    jump_count = k
    for stone in stones:
        if stone <= mid:
            jump_count -= 1
            if jump_count == 0:
                return False
        else:
            jump_count = k
    return True

def solution(stones, k):
    niniz = 0
    left = 0
    right = 200000000
    
    while left <= right:
        # 니니즈 친구들의 수
        mid = (left + right) // 2
        
        if niniz_jump(stones, k, mid):
            niniz = mid
            left = mid + 1
        else:
            right = mid - 1
            
    return niniz + 1

 

이분탐색으로 푸는 문제이다.

 

구해야 하는 것은 건널 수 있는 니니즈 친구들의 수이다. 이 니니즈 친구들의 수를 mid로 두고, niniz_jump함수에서 각각의 stone과 비교를 할 것 이다. 각 stone의 크기는 200,000,000이하인 자연수 이므로 left를 0, right를 200,000,000으로 둔다. 정답을 찾을 때 까지 niniz_jump를 통해 확인한다. niniz_jump에서는 각 돌이 니니즈 친구들을 몇 명까지 버틸 수 있는지를 본다.

 

for stone in stones:
        if stone <= mid:
            jump_count -= 1
            if jump_count == 0:
                return False
        else:
            jump_count = k

 

위와 같이 해당 인덱스의 돌이 mid보다 작거나 같으면 mid번 째에 해당하는 니니즈가 해당 stone을 못 건넌다고 간주하고 jump_count에서 1을 빼준다. 클 경우 jump_count를 다시 k로 초기화 시킨다. 이것을 각 stone마다 반복하고, jump_count가 0이 되면 점프해서도 갈 수 없으므로 false를 반환한다.

 

if niniz_jump(stones, k, mid):
            niniz = mid
            left = mid + 1
        else:
            right = mid - 1

 

false를 반환한 경우, 니니즈의 수인 mid가 너무 큰 경우 이므로 right를 mid-1로 초기화 시켜주고 true인 경우, mid에 해당하는 니니즈가 충분히 건널 수 있으므로 niniz에 mid값을 넣고 left를 mid+1로 초기화 시켜서 더 큰 값을 검사한다.