[프로그래머스] 징검다리 건너기 [Level 3] (python 파이썬)
https://school.programmers.co.kr/learn/courses/30/lessons/64062
def solution(stones, k):
stone_min = min(stones)
stone_max = max(stones)
if stone_min == stone_max:
return stone_min
while 1:
n = 0
now = (stone_min + stone_max)//2
c = 0
for stone in stones:
if stone - now < 0:
n = n+1
if n == k:
stone_max = now
c =1
continue
else:
n = 0
if c == 0:
stone_min = now
if (stone_min+stone_max)//2 == now:
return now
이 문제는 이분탐색을 통해 해결할 수 있다.
stones 배열의 크기는 200,000 이하 이며, 각 원소의 값은 200,000,000 이하이므로, 문제를 처음 봤을 때 가장 처음 먼저 드는 아이디어는 시간 초과 오류가 났다.
stones를 돌면서 1개씩 빼가며, 한 명씩 건너는 것을 구현하고, 0보다 작은 연속된 구간이 k인 경우 건넌 사람을 리턴하는 방법은 입력값이 매우 큰 경우 시간 오류가 날 것이다.
따라서 stones를 모두 도는 연산을 최소화 할 필요가 있다.
위의 경우에는 1개씩 늘면서 개산하므로 적어도 stones의 최소값 만큼을 stones를 돌 것이다.
건너는 사람의 수의 범위는 최소값 부터 최대값까지 이다.
건너는 사람의 수 = (최소값 + 최대값)//2
최소값 <= 건너는 사람의 수 <= 최대값
건너는 사람의 수가 정답보다 큰 경우에는 연속된 0보다 작은 수가 k번 이상일 것이다.
이 경우에는 최대값을 줄여서 건너는 사람의 수를 줄여야 한다.
최대값 = 건너는 사람의 수로 변경 (적어도 건너는 사람의 수보다는 답이 작을 것이므로)
반면에 건너는 사람이 모두 잘 건너고 나면, 이 경우는 건넌 사람의 수가 정답보다 작을 가능성이 있다.
이 경우에는 최솟값을 늘려서 건너는 사람의 수를 늘려야 한다.
최소값 = 건너는 사람의 수로 변경 ( 적어도 건너는 사람의 수보다는 답이 클 것이므로 )
위의 과정을 반복하면서 건너는 사람의 수를 반복할 때, 이전의 수와 현재의 수가 동일 한 경우가 올 것이다.
그 때의 수를 리턴한다.