문제 설명
카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.
-
징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
-
디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
-
단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.
"니니즈 친구들"은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
"니니즈 친구들"은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.
디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.
제한사항
-
징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
-
stones 배열의 크기는 1 이상 200,000 이하입니다.
-
stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
-
k는 1 이상 stones의 길이 이하인 자연수입니다.
입출력 예
| stones | k | result |
|---|---|---|
| [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] | 3 | 3 |
CASE 1) 효율성 테스트 실패
def solution(stones, k):
windows = [max(stones[:k])]
for i in range(k, len(stones) - k+1):
num = max(stones[i:k+i])
windows.append(num)
return min(windows)brute force를 이용해 K 범위 안에서 가장 큰 원소들을 뽑아 그중에 가장 작은 수를 찾는 방법으로 풀었고 정확성 테스트는 모두 통과 했으며 코드의 길이가 짧아서 마음에 들었으나
- stones 배열의 크기는 1 이상 200,000 이하입니다.
- stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
위의 제한사항 때문에 배열이 크거나 원소들의 값이 클 경우 효율성 테스트를 통과하지 못하는 것으로 보인다.
CASE 2) 효율성 테스트 성공
Sliding Window와 Deque 자료구조를 이용해서 풀이하는 방법.
슬라이딩 윈도우 알고리즘은 처음 접해보는 개념이라 흥미로웠다.
from collections import deque
def solution(stones, k):
stones = list(zip(range(1, len(stones) + 1), stones))
q = deque()
answer = float("inf")
for idx, val in stones:
while q:
if q[0][0] <= (idx - k):
q.popleft()
elif q[-1][1] < val:
q.pop()
else:
break
q.append((idx, val))
if idx >= k:
answer = min(q[0][1], answer)
return answer
효율성 테스트때문에 골치가 아팠으나, 질문하기 란에 O(n) 시간복잡도 풀이법 힌트
글을 보고 힌트를 얻어 풀 수 있었다. (감사합니다ㅠㅠ)
stones배열을(index, value)쌍으로 매핑한 뒤 순회Deque에 뒤에서부터 집어넣기Deque의 마지막 원소가 집어넣을 원소보다 작다면,popDeque의 첫번째 원소가 현재index - k를 벗어났다면,pop결과적으로
Deque[0]가 해당 구간의 최대 값이 되며
Deque 자료구조는 head 와 tail 의 삽입, 삭제가 모두O(1)이다.
answer 은 여기서 구해진 최대 값 중 가장 작은 값이 된다.
Reference
https://school.programmers.co.kr/questions/41064
https://velog.io/@zwon/%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0Sliding-Window
