[이분탐색] 징검다리

코딩테스트 연습 - 징검다리 | 프로그래머스 (programmers.co.kr)

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

 

 내가 제일 싫어하는 이분탐색이다.

이분탐색은 항상 어렵다. 사실 어떻게 풀어야 될지도 모를 것 같기 때문이다.

 

 일단 이분탐색으로 업다운 할 것을 정해야한다. 쉬운 이분탐색 문제라면 답으로 구할 것을 이분탐색하겠지만, 이 문제에서는 어떨까? 

 

 이 문제의 목적은 '최솟값 중에 가장 큰 값'이다. 일단 바위를 제거하지 않고 순회를 돈다. 예시에선 바위가 [2, 11, 14, 17, 21] 이고, 여기서 시작점과 도착점이 추가된다. 지금 생각하고 있는 것은 키값을 잡고, 바위를 순회한다. 바위 사이의 거리가 키값보다 높다면 pass, 낮다면 그 바위를 건너뛰고 다음 바위와의 거리를 계산한다. 그리고 누적 카운트에 1을 더한다. 이것이 제거한 바위가 된다. 만약 이 카운트가 제거해야할 바위 갯수보다 많아진다면, 키값을 늘리고 다시 시작한다.

 

 즉, 대부분의 돌 간의 거리는 현 키값보다 커야한다. 작을 경우에는 2번(n번)의 기회를 줘서 (돌을 건너 뛰어서) 순회한다. 만약 n번을 초과한다면, 거리를 1 늘리고 다시 한다.

 

 하지만, 이렇게 코드를 작성한다면 무한 루프를 돌 것이다. 그렇다면 종결 조건은 어떻게 둬야할까?

 

 우선 제일 작은 값 (1이라던가) 으로 둬서, 점점 늘리다가 만약 돌을 2개 제거하지 않고도 순회가 가능하다면 멈춘다. 그리고 구하고 싶은 것은 '최솟값 중의 최댓값' 이므로 가장 마지막의 키값이 답이 될 것이다.

 

 그리고 시작 키값을 생각해보자. 거리가 될 수 있는 가장 작은 값은 0이고 가장 큰 값은 distance이다 (엄밀히 말하면 distance는 될 수 없다.). 그래서 이 값을 low, high로 놓고 mid는 이 중간값을 취한다.

 

 그래서 돌을 순회하면서 돌 사이의 거리 (dis) 와 mid 거리를 비교한다. 세부 코드는 밑과 같다. 

 

def solution(distance, rocks, n):

    rocks.sort()
    rocks.append(distance)
    low = 0
    high = distance
    mid = (low + high) // 2

    while (low <= mid):
        prev = 0
        rmCnt = 0

        for i in range(len(rocks)):
            dis = rocks[i] - prev
            if (dis < mid):
                rmCnt += 1
            else:
                prev = rocks[i]
        
        if (rmCnt <= n):
            low = mid + 1
        else:
            high = mid - 1
        mid = (low + high) // 2
    return mid

 코드 해석은 다음과 같다. prev 는 이전 돌의 위치이고, rocks의 마지막 돌(distance)를 추가한다. 그리고 rocks를 순회하면서 prev와 비교한다.

 

 만약 rocks[idx] - prev (돌 간 거리) 가 mid(현재 키값) 보다 작다면 돌을 제거해야한다는 의미이다. 그래서 삭제한 돌 수(rmCnt)를 1증가시키고 다음 돌로 넘어간다. 

 그래서 현재 돌과 이전 돌 사이의 거리가 mid보다 크다면 괜찮다는 말이다. prev를 현재 돌로 갱신해주자. (이 때문에 시작점 0을 prev 초기값으로 해주고, 마지막 돌 위치인 distance를 rocks의 맨 마지막에 추가하는 것이다.)

 

 그리고 순회가 끝난 뒤, 삭제한 돌 수(rmCnt)가 제거해야하는 돌 수(n) 이하라면, mid값이 작기 때문에 좀 더 키워도 된다는 말이다. rmCnt > mid의 경우에는 mid 값이 커서 필요 이상의 돌을 건너 뛰어야한다는 말이므로 mid값을 줄인다.

 

 이 때, rmCnt < n이 아닌, <=를 쓴 이유는, mid값이 달라도 같은 갯수(n)의 돌을 제거할 수도 있기때문이다. 그런데 우리가 구하고자 하는 것은 '최솟값 중의 최댓값'이므로, n개의 돌을 제거하는 mid값들 중 가장 큰 값을 찾아야하기 때문에 저렇게 썼다.

 

 이렇게 해서 이 문제를 풀 수 있다.

 

통과

예전보다는 어떤 값을 이분탐색으로 찾아야할 지에 대해서 알게된 것 같긴하지만 역시 이분탐색은 어렵다. 조금 더 공부하고 싶다.