문제 설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한사항
- prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
- prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
| prices | return |
| [1, 2, 3, 2, 3] | [4, 3, 1, 1, 0] |
입출력 예 설명
- 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
- 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
- 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
- 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
- 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
※ 공지 - 2019년 2월 28일 지문이 리뉴얼되었습니다.
푸는 방법과 시간복잡도
푸는 방법은 세 가지 -> 완전탐색, queue, stack
처음에 완전탐색으로 풀어보고 queue 로 풀었다.
완전 탐색과 최악의 상황에서의 queue 는 O(N^2) 인데 비해 stack 은 O(N) 이다.
코드
queue 사용
from collections import deque
def solution(prices):
answer = []
prices_q = deque(prices)
while len(prices_q) != 0:
period = 0
current_val = prices_q.popleft()
for val in prices_q:
period += 1
if current_val > val:
break
answer.append(period)
return answerstack 사용
def solution(prices):
answer = [0] * len(prices) # 결과를 저장할 배열 (초기값 0)
stack = [] # 가격이 떨어지지 않은 인덱스를 저장하는 스택
for i, price in enumerate(prices):
# 스택이 비어있지 않고, 현재 가격이 스택의 top보다 낮으면
while stack and prices[stack[-1]] > price:
j = stack.pop() # 스택에서 인덱스 꺼내기
answer[j] = i - j # 가격이 떨어진 시점 계산
stack.append(i) # 현재 인덱스를 스택에 저장
# 스택에 남아 있는 인덱스들은 끝까지 가격이 떨어지지 않은 경우
while stack:
j = stack.pop()
answer[j] = len(prices) - 1 - j
return answer
내가 배울 점
stack 코드는 챗지피티가 설명해준 코드라 실제 검색해서 나오는 코드는 아닌데, 실제 검색해서 나오는 코드는 처음에 희망회로를 잔뜩 돌린 계속 주식이 오른다! 의 경우로 배열을 세팅해둠 [5,4,3,2,1] 이런 식으로.
python 에서 queue 는 deque, stack 은 list 를 사용한다.
풀 때 설계를 작성을 하고(손으로 하고 주석으로도 하고.) 시간복잡도까지 생각하면서 해보기.
오늘은 급한 마음을 추스리고 손으로 적어보고 완전탐색으로 풀고, 큐로는 어떻게 풀어야 하나 손으로 해보고 풀어보니 음 좀 되는데 생각이 들었다. 물론 문제 이해를 잘 했다는 가정 하에.. 급하게 하지 말고 찬찬히 풀어보는 게 중요하고 여러 방법들을 찾아보면서 이해하려고 해보니까 머리에 더 남는 느낌이다. (오늘이 주말이라 그런가? 모르겠다.)
728x90
반응형
