[Python][프로그래머스] 주식 가격 / 스택 (Lv2)

🖇️ 링크 

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

---

🗒️ 파이썬 코드 풀이

def solution(prices):
    answer = [0] * len(prices)
    stack = []
    
    for idx,value in enumerate(prices):
        while stack and stack[-1][1] > value:
            print(1)
            k, _ = stack.pop()
            answer[k] = idx -k 

        stack.append((idx,value))
       
    while stack:
        idx,_ = stack.pop()
        answer[idx] = len(prices) - idx - 1
        
    return answer

 

시간 복잡도 O(N)

 

1. 이중 for문으로 완전 탐색을 하면 편하겠지만, 아쉽게도 범위가 100,000 이하이다.

 

2. Stack을 이용해서 문제를 푸는 방식으로 진행해야한다. 

• answer, stack 리스트를 만들어준다.

 

3. prices[idx] (현재의 값)이 stack[-1][1]의 마지막 값보다 큰 경우

• 계속 떨어지지 않는 경우이므로 stack에 append 하고 나중에 한번에 처리

 

4. prices[idx] (현재의 값)이 stack[-1][1]의 마지막 값보다 작은 경우

• 이 경우 값이 떨어진 경우이기 때문에, 가장 최근 stack을 계속 pop 하면서 answer를 채움

 

5. 마지막은 stack에 넣어진 값들을 하나씩 pop하면서 answer 값 채운다.

---

📌  문제 코멘트 

 

 

LV 2 이지만, 개인적으로 어려웠던 문제이다.

어떻게서든 for문을 2번 안쓰려고 하였던게 문제였다.

 

해당 문제 풀이에서는 for문 while을 같이 쓰는데, 이와 같은 경우 문제가 되지 않았다. 

이유는 while 문이 진행되는 경우는 전체 prices 크기만큼만 진행되기 때문이다.

그래서 비록 for 문이 있지만, 시간 복잡도가 O(N)이 되는 것이다. 

 

그리고 또한 stack에 인덱스를 저장해서 문제를 푸는 것도 신기했다 .