[python] 스택/큐_주식가격(2단계)

문제 설명

1. 주식가격

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

2. 제한 조건

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

3. 풀이 과정

def solution(prices):
    answer = [0]*len(prices)
    stack = []
 
    for i, price in enumerate(prices):
        #stack이 비었이면 false
        while stack and price < prices[stack[-1]]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
 
    # for문 다 돌고 Stack에 남아있는 값들 pop
    while stack:
        j = stack.pop()
        answer[j] = len(prices) - 1 - j
 
    return answer

스택에서 꺼낸 값(인덱스)과 반복문 현재 위치에 있는 값의 주식 가격을 비교한다.

for문을 돌고있는 i가 현재 시간이라고 생각하면 된다.

비교하는 과정에서 스택에서 꺼낸 값보다 현재 시점의 주식 가격이 떨어졌다면,
현재 시점과 스택에서 꺼낸 값의 차를 저장한다.

주식 가격이 떨어지지 않았다면,
지금까지 스택에 남아있는 값은 현재 시점까지 계속 오르고 있다는 말이다.

스택에서 값을 꺼내지 않고 다음 위치로 넘어간다!

이 풀이에서 핵심은 (시간의 흐름대로) 반복문을 계속 진행하면서
현재 시점보다 가격이 높은 시점이 언제였는지 되짚어가면서 판단하는 방식이다.

def solution(prices):
    # answer = 몇초 후 가격이 떨어지는지 저장하는 배열
    answer = [len(prices)-i-1 for i in range(len(prices))]
    
    # stack = prices의 인덱스를 차례로 담아두는 배열
    stack = [0]
    
    for i in range(1, len(prices)):
        while stack:
            index = stack[-1]
            
            # 주식 가격이 떨어졌다면
            if prices[index] > prices[i]:
                answer[index] = i - index
                stack.pop()
       
            # 떨어지지 않았다면 다음 시점으로 넘어감 (주식 가격이 계속 증가하고 있다는 말)
            else:
                break
        
        # 스택에 추가한다.
        # 다음 시점으로 넘어갔을 때 다시 비교 대상이 될 예정이다.
        stack.append(i)
        
    return answer

추천수 높은 풀이

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