[프로그래머스/코딩테스트 연습/Lv.2] 주식가격-파이썬(Python)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

 

---

풀이

def solution(prices):
    answer=[0]*len(prices)
    stack=[] # 주식의 시점과 그때의 가격을 나타내는 스택
    for i,v in enumerate(prices):
        while stack and v<stack[-1]['value']: # 스택의 마지막 원소의 가격보다 현재 가격이 떨어졌으면 반복
            answer[stack[-1]['time']-1]=i+1-stack[-1]['time'] # 스택의 마지막 원소의 가격이 떨어지지 않은 기간을 구한다. (i+1은 현재 시각)
            stack.pop() # 그리고 그 원소를 스택에서 꺼낸다.
        stack.append({'time': i+1, 'value':v})
    for i in stack: # 남아 있는 원소들은 끝까지 가격이 떨어지지 않은 것들이다.
        answer[i['time']-1]=(len(prices)-i['time']) # len(prices)는 마지막 시점과 같음
    return answer

---

Tip

• 이 문제는 언뜻 보면 이중 반복문을 사용해야 할 것 같지만, 스택을 사용하면 이중 반복문을 사용하지 않고 풀 수 있다.
• 스택의 원소들은 주식의 시점과 그때의 가격을 나타내는 dictionary들이다. (ex. {'time': 1, 'value': 1})
• (위 코드에서) 스택을 사용하는 이유는 다음과 같다:
  스택에 원소를 넣을 때 "현재 가격이 스택의 마지막 원소의 가격보다 떨어졌을 경우, 스택에서 마지막 원소를 꺼내는 과정"을 반복한다. 이렇게 하면 스택에 있는 원소들은 첫 원소부터 마지막 원소까지 가격을 기준으로 오름차순으로 존재하게 된다. 또한, 그렇게 되면 스택의 원소를 넣을 때, 현재 가격이 스택의 마지막 원소의 가격보다 떨어지지 않았을 경우, 스택에 존재하는 그 이전의 원소들은 확인할 필요가 없기 때문에 시간을 매우 줄일 수 있다.
• 가격이 떨어지지 않은 기간들은 스택에서 원소를 꺼낼 때 정해진다. 가격이 떨어지지 않은 것들(스택에 남아 있는 원소들)은 마지막에 한꺼번에 그 기간을 정한다.

---

TIL

없음