문제 설명:
카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.
- 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
- 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
- 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.
"니니즈 친구들"은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다. "니니즈 친구들"은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.
디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.
제한사항
- 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
- stones 배열의 크기는 1 이상 200,000 이하입니다.
- stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
- k는 1 이상 stones의 길이 이하인 자연수입니다.
풀이:
1. 첫 번째 아이디어 k개 범위의 슬라이딩 윈도우를 해주고 만약 k개 씩 슬라이딩 윈도우를 하면 가장 큰 값 만큼 건널수 있다.
예를들면
1342 일경우에는
134, 342 이렇게 두 경우인데, 4명, 4명이 건널 수 있는것이다.
모든 돌을 다 건너야 하기 때문에 그중에 가장 최솟값을 선택해야한다고 생각했다.
count = 1
number = [max(stones[0:k + 1])]
for i in range(1, len(stones) - k + 1):
number.append(max(stones[i:i+3]))
number.sort()
return number[0]
맞는거 같은데. 1개만 맞고 다 틀린다. 무슨 문제가 있나보다.
그래서 문득 저번에 푼 백준 - 최솟값찾기
(Python/플5)백준알고리즘 11033번: 최솟값 찾기
문제 바로가기 문제: N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한
windy7271.tistory.com
이 문제를 풀때 고생했던 기억이 떠올랐고 사실상 같은 로직이라고 생각했다.
from collections import deque
def solution(stones, k):
result = deque()
answer = []
# 슬라이딩 윈도우 최솟값 저장
for idx in range(len(stones)):
# 처음과 마지막 인덱스 값이 k개 이하 여야함
if result and result[0][0] <= idx - k:
result.popleft()
while len(result) >= 1 and stones[idx] > result[-1][-1]:
result.pop()
result.append((idx, stones[idx]))
answer.append(result[0][1])
return min(answer[k-1::])
자세하게 설명을 해보자면
if result and result[0][0] <= idx - k:
result.popleft()
result가 들어가 있고. result에 크기가 k보다 안 커지게 유지해준다. 즉 슬라이딩 윈도우 범위를 넘어가게 되면 삭제한다.
while len(result) >= 1 and stones[idx] > result[-1][-1]:
result.pop()
result.append((idx, stones[idx]))
answer.append(result[0][1])
result에 마지막 값보다. 새로온 돌이 크면 큰 돌이 나올때까지 빼주고 새로운 돌을 넣어준다.
그리고 answer에 첫 값을 넣어주면
그게 k개의 슬라이딩 윈도우 중에서 가장 큰 값이 되게 된다.
댓글