[Programmers] 징검다리 건너기 문제 풀이 (Python)

1. 문제 풀이

이분 탐색을 활용한 파라메트릭 서치(Parametric Search)를 이용하여 푸는 방법이다.

파라메트릭 서치(Parametric Search)

최댓값, 최솟값 등을 찾는 최적화 문제를 결정 문제로 바꾸어 푸는 방법이다.

• 현재 문제: 징검다리를 건널 수 있는 사람이 최대 몇 명인가? → t명
• 결정 문제: k명의 사람이 징검다리를 건널 수 있는가? → True or False

결정 문제로 바꾸었을 때 장점은 탐색 공간을 줄일 수 있다는 것이다. 예를 들어, k명의 사람이 징검다리를 건널 수없다고 가정해보자. 그렇다면 k+1명의 사람도 건널 수 없으므로 1 ~ k-1까지의 숫자 중에서 건널 수 있는 사람의 최대 수를 찾으면 된다.

보통 이분 탐색을 이용해 탐색 공간을 줄이며 탐색할 때마다 True or False인지 판별하여 정답을 구하게 된다.

# Pseudo-code
while left <= right:
		mid = (left + right) // 2
		if check(mid): # mid가 문제에서 주어진 조건을 만족하는지 check!
				result = mid
				left = mid + 1
		else:
				right = mid - 1

최적화 문제를 결정 문제로 바꾼다고 해서 꼭 더 빠르다는 것은 아니다. True or False 인지를 판별하는 함수의 시간복잡도가 느리다면 결국 바꿔서 풀어도 더 느릴 수 밖에 없다.

예를 들어 최적화 문제로 풀었을 때 시간복잡도가 $O(N^2)$이라고 하고 True or False 인지를 판별하는 함수 또한 $O(N^2)$이라고 해보자. 여기에 이분 탐색의 시간 복잡도를 곱해주어야하기 때문에 결과적으로 결정 문제로 풀었을 때 시간 복잡도가 더 커지게 된다. 따라서 파라메트릭 서치로 문제를 풀 때 True or False 인지를 판별하는 함수의 시간복잡도를 고려하여 풀어야한다.

파라메트릭 서치 정리

• 이분 탐색을 사용하기 때문에 이분 탐색의 조건을 만족해야한다.
  • 전체 탐색 공간 크기가 정해져있으며 정렬되어있어야한다.
  • k가 되지 않는다면 k+1도 되지 않는다는 조건을 만족해야한다. 반대로 k가 된다면 k-1도 된다는 조건을 만족해야한다. 즉, 탐색 공간을 줄일 수 있어야한다.
• True or False 인지를 판별하는 함수의 시간복잡도를 고려해야한다.
  • $O(n)$ 이내에 판별할 수 없다면 쓰지 않는 것이 좋다.

최종

• 이분 탐색
• Yes or No 판별하는 함수: t명이 모두 건넜을 때 디딤돌 숫자가 0보다 작으면 그 디딤돌을 t명이 밟고 건널 수 없다는 뜻이다. 따라서 t를 뺏을 때 디딤돌 숫자가 음수인 것이 연속으로 k개가 존재한다면 t명이 건널 수 없다.

2. 코드

def promising(stones,mid,k):
    cnt = 0
    for s in stones:
        if s >= mid: cnt = 0
        else: cnt += 1

        if cnt == k:
            return False
    return True

def solution(stones,k):
    left, right = 1,sum(stones)
    result = 0
    while left <= right:
        mid = (left + right) // 2
        if promising(stones[:],mid,k):
            left = mid + 1
            result = mid
        else:
            right = mid - 1
    return result