📍 문제

[프로그래머스] Lv.2 주식가격

📍 주요 개념

📚 스택(Stack)

• 후입 선출 구조(Last In First Out)로 나중에 들어간 것이 먼저 나오는 구조
• 파이썬에서는 별도의 라이브러리 없이 기본 리스트로 구현하고, append()와 pop()을 이용해 스택을 구현할 수 있다.

스택 구현

stack = []

stack.append(1) # 삽입 O(1)
stack.pop() # 삭제 O(1)

stack[-1] # 삭제 하지 않고 최상단 원소 가져오기
print(stack) # 최하단 원소부터 출력
print(stack[::-1]) #최상단 원소부터 출력

📚 큐(Queue)

• 선입 선출 구조(First In First Out)로 먼저 들어간 것이 먼저 나오는 구조
• 별도의 라이브러리 없이 리스트를 사용하여 구현을 할 수 있지만 시간복잡도가 O(n)이기 때문에 라이브러리를 사용해서 구현해주는 것이 좋음!
• collections에서 제공하는 deque를 사용한다.

from collections import deque

pop(): 오른쪽(마지막) 값 출력 시
popleft(): 왼쪽(처음) 값 출력 시
append(): 오른쪽에 값 입력
appendleft(): 왼쪽에 값 입력

큐 구현

from collections import deque
list = []
queue = deque(list) 

queue.append(1) # 삽입 O(1)
queue.popleft() # 삭제 O(1)

📍 풀이 (Queue)

• 스택/큐 카테고리에 있어서 큐를 이용하기로 했다.
• 현재 가격을 .popleft()로 맨 앞 원소를 추출해주고 반복문을 돌면서 큐 안의 원소보다 크다면 time을 1씩 증가시켜준다.
• 현재 가격이 큐 안의 원소보다 작다면 break를 통해 반복문을 탈출하고, 해당하는 time을 answer에 append해준다.

💻 코드

from collections import deque

def solution(prices):
    answer = []
    prices_q = deque(prices)
    
    while prices_q:
        price = prices_q.popleft()
        time = 0
        for q in prices_q:
            time += 1
            if price > q:
                break
        answer.append(time)
    return answer

별로 어려운 문제가 아니라 쉽게 통과했지만, 다른사람들의 풀이를 참조하고 싶어서 구글링 한 결과 스택을 이용하면 시간복잡도측면에서 훨씬 이득이라는 것을 발견!

📍 풀이 (Stack)

큐를 이용하면 맨 앞의 값을 popleft()해서 그 가격을 뒤의 가격들과 비교만 하면 되는데 스택을 이용할 땐 가격을 어떻게 비교하는지 감이 잘 잡히지 않았다.
그래서 좋은 벨로그 글을 공유합니닷 👉참조한 글
스택을 이용하여 어떻게 풀었는지 자세하게 설명해주셨다.

💻 코드

def solution(prices):
    length = len(prices)
    
    # answer을 max값으로 초기화  
    answer = [ i for i in range (length-1, -1, -1)]
    
    # 주식 가격이 떨어질 경우 찾기
    stack = [0]
    for i in range (1, length):
        while stack and prices[stack[-1]] > prices[i]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

내 방식대로 이해한 알고리즘을 적자면

1. answer를 값이 '떨어지지 않는다' 는 가정을 한 리스트로 바꾼다.
   (prices = [1, 2, 3, 2, 3]이라면, answer = [4, 3, 2, 1, 0] 이렇게)
2. 주식 가격이 떨어질 경우를 찾는다.
   prices를 순회할 때 주식 가격이 계속 오르고 있다면 answer는 수정할 필요가 없다.
   하지만 주식 가격이 떨어진다면
   1. stack에 저장된 인덱스와 비교(stack에는 현재 순회하는 인덱스가 append됨)
   2. 감소하는 경우라면 해당 answer의 값을 주식가격이 감소할 때의 인덱스 - stack의 인덱스로 answer에 값을 업데이트

이런식인데, stack에는 현재 순회하는 인덱스를 append 해주고, while문은 가격이 떨어질 경우에 수행하는 반복문이다.
만약에 가격이 떨어진다면, stack의 최상단의 원소를 pop해주고(현재 순회하는 인덱스가 가격이 떨어지는 시점이므로) answer에 시간을 계산해서 담아준다. 이를 stack이 빌 때 까지 반복
큐 보다 구현하기 어렵지만 시간복잡도 측면에선 2배 정도 이득이라 알아두면 좋은 방법인듯 하다!!