[고득점 Kit / 스택&큐] 주식가격

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

프로그래머스

 

이 문제는 2가지 방법으로 풀 수 있다.

1. 스택을 이용한 방법

2. 이중반복문을 이용한 방법

 

당연히 스택을 이용하여 푸는 것이 출제의도겠지만, 10,000이하의 자연수이기도 하고, 시험장에서 스택풀이가 생각나지 않으면 이중반복문이라도 써서 풀어야 한다.

 

1. 스택을 이용한 방법

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

    for i in range(n):
        while stack and prices[i] < prices[stack[-1]]: # i의 이전 인덱스와 비교했을 때 이전 인덱스가 더 크다면 주식 가격이 하락했다는 의미
            idx = stack.pop() # 주식 가격이 하락하기 이전의 인덱스를 idx에 저장
            answer[idx] = i - idx  # 주식 가격이 하락하기 이전의 인덱스의 자리에 주식가격이 하락하지 않은 시간을 저장
        stack.append(i) 

    while stack: # 스택에 아직 값이 남아 있다면
        idx = stack.pop() # 스택의 인덱스가 큰 순서부터 idx에 값을 저장
        answer[idx] = n - 1 - idx # 해당 idx에 대한 원소값(주식가격이 하락하지 않은 시간)을 answer에 저장

    return answer

 

 

1. prices 배열을 순회하며 각 시점의 가격에 대해 검사한다.
2. 현재 가격보다 작은 값이 나오는 시점을 찾을 때까지 스택에 저장된 값을 꺼내어 가격이 떨어진 시간을 계산한다.
3. 모든 시점을 순회한 후, 스택에 남아있는 값들에 대해서는 남은 시간동안 가격이 떨어지지 않았으므로 끝까지 유지된 시간으로 처리한다.

코드를 하나하나씩 뜯어보자.

 

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

 

 

 

• answer: 결과를 저장할 배열로, 각 시점에서 가격이 유지된 기간을 저장
• stack: 가격이 떨어지지 않은 인덱스를 저장할 스택

 

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

 

 

i를 0부터 n까지 반복하면서 현재 가격이 이전에 스택에 저장된 가격보다 작을 때까지 스택에서 값을 꺼내서 answer에 떨어지지 않은 기간을 기록하고, 기록이 끝나면 현재 인덱스를 스택에 넣는다.

 

이 부분이 이해가 잘 가지 않을 수 있으므로, 동작과정을 살펴보자.

 

 

• 첫 번째 루프 (i=0, 가격 1)
  • 스택이 비어있으므로, stack = [0] (인덱스 0을 추가)
• 두 번째 루프 (i=1, 가격 2)
  • 스택의 마지막 가격 (prices[0] = 1)이 현재 가격 2보다 작으므로, 아무 작업도 하지 않고 stack = [0, 1] (인덱스 1을 추가)
• 세 번째 루프 (i=2, 가격 3)
  • 스택의 마지막 가격 (prices[1] = 2)이 현재 가격 3보다 작으므로, stack = [0, 1, 2] (인덱스 2를 추가)
• 네 번째 루프 (i=3, 가격 2)
  • 스택의 마지막 가격 (prices[2] = 3)이 현재 가격 2보다 크므로, 스택에서 값을 꺼냅니다.
    • 인덱스 2에서 가격이 떨어졌으므로, answer[2] = 3 - 2 = 1
    • stack = [0, 1]
  • stack = [0, 1, 3] (인덱스 3을 추가)
• 다섯 번째 루프 (i=4, 가격 3)
  • 스택의 마지막 가격 (prices[3] = 2)이 현재 가격 3보다 작으므로, stack = [0, 1, 3, 4] (인덱스 4를 추가)

 

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

 

 

만약 스택에 남아있는 인덱스가 있다면, 이는 해당 시점 이후로 가격이 떨어지지 않은 경우이므로,  n-1 (마지막 인덱스)까지 떨어지지 않은 기간을 계산한다.

 

스택에 남은 값 처리

• 루프가 끝났으므로 스택에 남아있는 값들을 처리
• 인덱스 4: 마지막까지 가격이 떨어지지 않았으므로 answer[4] = 5 - 4 = 0
• 인덱스 3: 마지막까지 가격이 떨어지지 않았으므로 answer[3] = 5 - 3 = 1
• 인덱스 1: 마지막까지 가격이 떨어지지 않았으므로 answer[1] = 5 - 1 = 3
• 인덱스 0: 마지막까지 가격이 떨어지지 않았으므로 answer[0] = 5 - 0 = 4

 

이렇게 제출하면 정답이다.

 

 

2. 반복문을 이용한 방법

시간복잡도가 별로이긴 하지만, 그래도 정답처리가 된다. 그리고 아마 많은 사람들이 이걸로 답을 제출했을거라 생각한다.

시험장에서 1번풀이가 생각나지 않으면 이렇게라도..

def solution(prices):
    answer = [0] * len(prices)
    for i in range(len(prices)):
        for j in range(i+1, len(prices)):
            if prices[i] <= prices[j]:
                answer[i] += 1
            else:
                answer[i] += 1
                break
    return answer