[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