징검다리

문제정의

---

징검다리에서 돌을 빼냈을 때 벌어지는 간격의 최솟값이 가장 큰 것을 구하는 것이다. 문제는 여기에서 볼 수 있다.

문제풀이

---

이진 탐색을 이용한 문제이다. 유형을 익히면 반가운 문제이지만, 처음에 보면 전혀 감이 안 잡힌다.

전체 코드는 다음과 같다.

def solution(distance, rocks, n):
    
    def isFeasable(distance, rocks, n, k):
        cnt = 0
        pos = 0
        total = len(rocks)
        for rock in rocks:
            if rock - pos >= k:
                cnt += 1
                pos = rock

        if total-cnt <= n:
            return True

        return False

    answer = 0
    l = 0
    r = distance
    rocks.sort()
    while l < r:
        mid = (l+r) // 2
        if(isFeasable(distance, rocks, n, mid)):
            answer = mid
            l = mid+1
        else:
            r = mid
            
    return answer

print(solution(25, [2, 14, 11, 21, 17], 2))

전체적인 코드의 흐름은 다음과 같다. 1. 간격에 대해서 이분 탐색을 해볼 것이다. 이를 k라고 두자. 2. k의 가장 작은 경우는 0이고 가장 큰 경우는 distance이므로 l과 r로 둔다. 3. 이분 탐색을 하면서 만약 isFeasable을 만족한다면, 돌을 더 빼도 된다는 의미이다. 따라서 mid 값을 늘린다. 4. 아니라면 mid 값을 줄인다. 5. 아니면 answer를 반환한다.

여기서 왜 돌을 더 빼도 된다는 의미에 대해 알아보기 위해 isFeasable을 살펴보자

def isFeasable(distance, rocks, n, k):
    cnt = 0
    pos = 0
    total = len(rocks)
    for rock in rocks:
        if rock - pos >= k:
            cnt += 1
            pos = rock

    if total-cnt <= n:
        return True

    return False

매개변수로 distance, rocks, n, k를 받는다. cnt는 돌의 개수를 의미하고 pos는 현재 선택한 돌의 위치를 본다. total은 총 돌의 개수를 의미한다.

for 문의 의미는 최솟값 k만큼의 간격에 포함되는 돌들을 세겠다는 의미이다. 프로그래머스에서 나온 예제를 보면 돌이 [2, 11, 14, 17, 21]의 순서로 놓여있다. 가령 k가 6이라면 [11, 17]에 위치한 돌이 선택되고 cnt는 2가 된다. total에서 cnt를 빼면 몇 개의 돌이 빠졌는지 볼 수 있고 이 값이 n보다 같거나 작으면 True를 반환한다.

이하에서 True를 반환하는 이유가 있다. 아래의 그림을 보자.

k와 n의 관계

k값이 증가하면 n값도 증가한다. 최솟값이 증가하니 돌 사이의 간격이 더 넓어져야 하기 때문이다. 여기서 우리는 n을 만족하는 최대를 구하려고 한다. 그러면 l이 증가해야 하는 경우를 살펴보아야 한다. 그림을 보면 n의 값이 요구하는 값보다 작을 때 k가 증가해야 함을 볼 수 있다. 이 이유로 인해 비교 연산자 <=를 사용한 것이다.

테스트

테스트 화면

자바로 하다가 파이썬으로 넘어오니까 코드가 훨씬 간결해서 놀랐다. 이제부터라도 열심히 애용하겠다.