[Programmers] 주식가격 (Python 3)

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

 

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

---

정말.. 나에겐 꽤 매운 문제였다

힘겹게 이해는 되었으므로 빠르게 풀이를 써본다

 

대충 이중 for문 써야한다는건 감이 왔다.
그러나 주목할 점은 문제의 분류가 '스택/큐' 라는 것이다. 이중포문으로 몸빵하라는 문제가 아니다.

마지막 요소의 가격을 비교하는 문제니 큐보다는 스택으로 풀 수 있는 문제 같다.

대충 스택이 필요한 구조라는건 머리를 굴리면서 이해가 되었으나, 이걸 어떻게 구현해야할지 막막했다.

스택에 각 price를 넣고 pop하면서 가격 등락을 비교하는 방식으로 생각을 했었는데,

그러면 후에 인덱싱하기가 너무 더러워지겠더라...

 

---

 

결국 다른 사람의 풀이를 찾아본 결과, 그럼 인덱스를 스택에 넣으면 되는거였다는 사실을 깨닫고 감탄했다.
꼭 비교 대상(price)이 스택에 있어야할 이유는 없다.

깨달은걸 참고해서 코드를 짜봤다.

 

풀이

def solution(prices):
    n = len(prices)
    answer = [0]*n
    stack = []

    for i in range(n):
        while stack and prices[stack[-1]] > prices[i]:
            top = stack.pop()
            answer[top]=i-top

        stack.append(i)

    while stack:
        top = stack.pop()
        answer[top] = n-1-top

    return answer