[스택/큐] 프로그래머스 Lv2. 주식가격 - Python

🗂️ 문제

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

프로그래머스

 

 

💡 접근법

언제 주식가격이 떨어졌는지 알기 위해서는 타겟 하나에 대해 이후의 주식 가격을 매번 비교해야 한다. 즉, 가격이 떨어지지 않는 기간(초 단위)을 각각 계산한다. 하지만 이러한 접근법으로 구현할 경우 시간 복잡도는 O(N²)이다.

 

😎 내 코드

def solution(prices):
    answer = []
    
    for i, p in enumerate(prices):
        seconds = 0
        for j in range(i+1, len(prices)):
            seconds += 1
            if p > prices[j]:
                break
            
        answer.append(seconds)
    
    return answer

현재 가격(p) 이후의 가격들을 확인하며 떨어지지 않는 기간을 계산한다.

 

만약 현재 가격 p가 이후 가격인 prices[j]보다 크면, 가격이 떨어진 것으로 간주하고 루프를 종료한다.

그리고 계산된 가격이 떨어지지 않은 기간(seconds)을 저장한다.

 

👀 배운 코드

def solution(prices):
    stack = []
    answer = [0] * len(prices)
    
    for i in range(len(prices)):
        while stack != [] and stack[-1][1] > prices[i]:
            past, _ = stack.pop()
            answer[past] = i - past
        
        stack.append([i, prices[i]])
    
    for i, s in stack:
        answer[i] = len(prices) - 1 - i
    
    return answer

스택을 활용하여 주식 가격이 떨어지기까지의 시간을 계산하는 코드로, 스택을 사용하면 주어진 문제를 O(N) 시간 복잡도로 해결할 수 있다. 스택에는 아직 가격이 떨어지지 않은 주식 가격만을 저장하는 것을 목표로 한다.

 

1. 스택이 비어 있지 않으면, 현재 가격이 스택의 마지막 가격보다 작은지 확인:
   • stack[-1][1] > prices[i]:
     • 현재 가격이 이전 가격보다 작다면 가격이 떨어진 것이다. 따라서 스택에서 이전 가격을 제거하며, 가격이 떨어진 시간을 계산한다.
     • 계산된 시간: i - past (현재 시간 i에서 이전 시간 past를 뺌).
     • 결과를 answer[past]에 저장한다.
2. 스택이 비어 있으면, 현재 가격 추가:
   • 스택에는 아직 가격이 떨어지지 않은 시간과 가격을 저장한다.
   • 해당 인덱스에서 가격이 유지된 시간은 (마지막 인덱스 - 현재 인덱스)로 계산한다.

 

🧐 배운 점

• 스택에는 다음 두 가지 정보를 저장함으로써 문제풀이에 유용하게 활용될 수 있다.
  1. 가격의 인덱스 (시간 계산에 필요)
  2. 가격 값 (현재 비교 기준)
• 막연히 스택을 이용하는 게 아니라 스택에 어떤 값을 넣느냐가 효율적인 문제 풀이의 핵심 포인트인 것 같다.