https://programmers.co.kr/learn/courses/30/lessons/42584
문제
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한사항
- prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
- prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
입력 | [1, 2, 3, 2, 3]
출력 | [4, 3, 1, 1, 0]
- 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
- 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
- 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
- 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
- 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
풀이
1. queue 사용
지금까지 프로그래머스에서 풀었던 queue 문제들을 deque가 아닌 list로 풀어와서 이번에도 그렇게 풀었는데 정확성은 다 통과했지만 효율성은 통과하지 못했다. 그래서 deque로 풀었더니 바로 통과 !~! 이유를 찾아봤더니 첫번째 원소를 pop할 때 사용하는 list의 pop(0)과 deque의 popleft()의 시간 복잡도가 각 o(n)과 o(1)이기 때문이라고 했다. 앞에서 풀었던 문제들은 queue의 길이가 길지 않아서 효율성 테스트도 통과한 것 같다. 따라서 queue의 길이가 길어지면 눈치껏 deque를 쓰기로 꼬옥 약속하면 돼 ..~!
이렇게 deque 이중반복문으로 풀면 어려운 문제는 아니다.
prices에서 pop한 뒤 prices를 순회하며 pop한 값보다 크거나 같으면 count에 1을 더한다. 그렇지 않으면 count에 1을 더하고 break 한 뒤 answer에 count를 추가하면 된다.
2. stack 사용
queue로 풀고 다른 사람들 풀이과정도 찾아봤는데 stack으로도 풀 수 있다고 한다. (queue보다 효율도 훨씬 좋다고 함)
알고리즘은 다음과 같다.
먼저 answer의 값을 주식의 가격이 떨어지지 않았을 경우의 출력값으로 초기화한다. (입출력 예시를 사용해보면 [4, 3, 2, 1, 0]) 그 다음 stack을 [0]으로 초기화 시켜주고 prices를 순회하며 stack의 마지막 값을 인덱스로 한 price 값보다 현재 price의 값이 작을 경우 ( prices[stack[-1]] > prices[i] ) stack에서 pop 후 answer 값을 수정한다.
stack = [0]
for i in range (1, len(prices)):
while stack and prices[stack[-1]] > prices[i]:
j = stack.pop()
answer[j] = i - j
stack.append(i)요론 식으루!
간단한거마냥 써놨는데 사실 생각해내기 넘 어려운 거 같다 ,ㅎ,ㅎ,
다시 짜라해도 stack으로는 못짜겠다 ㅎㅎ~
코드
from collections import deque
def solution(prices):
answer = []
prices = deque(prices)
while prices:
count = 0
price = prices.popleft()
for p in prices:
if price > p:
count += 1
break
count += 1
answer.append(count)
return answer