문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/64062
🕒 Python 풀이시간: 15분
def func(stones,k,mid):
stack=0
for i in range(len(stones)):
if stones[i]>=mid:
stack=0
else:
stack+=1
if stack==k:
return False
return True
def binary_search(stones,k):
answer=0
start=1
end=max(stones)
while start<=end:
mid=(start+end)//2
if func(stones,k,mid):
answer=mid
start=mid+1
else:
end=mid-1
return answer
def solution(stones, k):
answer = 0
answer=binary_search(stones,k)
return answer징검다리 건너기: 최대 인원 수 찾기! 🌉👣
징검다리를 건널 수 있는 최대 명수를 구하는 문제이다. 이때 규칙이 있는데 가장 가까운 돌로 이동하면서 이동한 돌은 -1이 된다는 것이다. 즉, 한명이 지날 때마다. 모든 0보다 큰 모든 돌이 -1씩 줄어든다는 것이다.
이러한 규칙으로 인해 이렇게 사고에 접근할 수 있다. "매 인원마다 -1씩 돌에서 감소시키는 것이 아니라 따지는 돌의 최솟값을 +1씩 증가시키면서 따져 나가면 된다." 이렇기 때문에 더 나아가 이렇게 생각할 수 있다. "매번 특정 숫자 이상의 돌을 따지면 되면 된다." 이러한 사고로 이어진다. 그렇기에 범위가 1<=(돌의 숫자)<=2억 이기 때문에 순차적으로 따질 수 있는 이분탐색을 도입할 수 있다는 사고에 이를 수 있다. 추가적으로 매 이분 탐색마다 돌의 갯수만큼 탐색해서 떨어진 돌을 찾기 때문에 200,000회 이므로 시간 복잡도의 연산은 200,000xlog(200,000,000)이라고 할 수 있기 때문에 충분히 가능하다는 것을 알 수 있다.
이러한 사고의 흐름을 바탕으로 설계를 했으니 이제 코드만 짜면 된다. 이분탐색을 짜고 해당 mid에 따라서 떨어진 돌을 찾는 함수를 만든다. 만약 k보다 더 멀리 떨어진다면 범위를 줄이고 충분히 k를 포함하게 뛸 수 있다면 정답으로 저장하면서 숫자의 범위를 늘리면 된다.
이렇게 Python으로 프로그래머스의 "징검다리 건너기" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
