Programmers. 징검다리 건너기

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 징검다리 건너기

문제 풀이

정확성은 모두 통과했으나 효율성을 통과하지 못했다. 증가하는 값에 따라 건너뛰는 돌의 간격도 점점 커지는 단조증가 함수로 이진 탐색을 확용해야 했다.

탐색 범위는 주어진 배열의 최솟값부터 최댓값까지인데 사실 제한사항의 최소, 최대범위로 설정해도 무방하긴 하다. 이후 중간값에 대해 건널 수 있는 지 검사하는 함수를 별도로 작성해야 한다.

함수는 바위를 순회하면서 탐색값 이하면 탐색값 인원만큼 통과 후 빈공간이 되므로 간격 + 1을 하고 초과가 나오면 다시 0으로 초기화하되 중간에 간격제한 k만큼 생성되면 불가능하다고 판단하여 그대로 break한 뒤 간격을 리턴하고 그렇지 않으면 순회 마지막에 간격을 리턴한다. 최댓값이므로 일단 k-1의 upper bound 값을 구하면 간격을 k - 1로 만드는 값이 바로 다음 값을 받을 수 있다. 그리고 그 값이 건널 수 있는 최댓값이 될 것이다.

• 이진 탐색의 최소, 최대 경계를 주어진 바위들의 최솟, 최댓값으로 설정
• mid에 대해 탐색
• 바위를 순회하며 mid만큼 건널 때 다음 사람이 0이 되는지 판별, 간격 제한 k 이상이 되면 해당 탐색값으로는 건널 수 없음을 의미, break하고 그대로 반환
• k - 1 초과면 r을 mid로, k - 1이상이면 l을 mid + 1로 이동(upper bound)
• upper bound 결과는 간격을 k - 1로 만드는 값들을 모두 지나 k로 만드는 첫번째 값으로 그대로 리턴한다.

python 코드

def solution(stones, k):
    if len(stones) == 1:
        return stones[0]
    def check(v):
        cnt = 0
        for s in stones:
            if s <= v:
                cnt += 1
            else:
                cnt = 0
            if cnt == k:
                return cnt
        return cnt
    l, r = min(stones), max(stones)
    while l < r:
        mid = l + (r - l) // 2
        s = check(mid)
        if s > k - 1:
            r = mid
        elif s <= k - 1:
            l = mid + 1
    return l