[PS][스택/큐] 주식 가격

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

프로그래머스

 

 

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

 

문제 이해

prices 배열의 각 요소는 주식 가격을 나타내며, 인덱스는 시간을 나타냅니다. 우리는 각 시간별로 가격이 떨어지지 않은 기간을 계산해야 합니다.

 

예시1:

• prices = [1, 2, 3, 2, 3]
• n = 5 (prices의 길이)
• answer = [0, 0, 0, 0, 0] (결과 배열)
• stack = [] (인덱스를 저장하는 스택)

단계별 과정

1. 첫 번째 가격 처리 (i = 0):
   • prices[0] = 1
   • 스택이 비어있으므로 stack.append(0) 수행
   • 스택 상태: [0]
2. 두 번째 가격 처리 (i = 1):
   • prices[1] = 2
   • 현재 가격(2)이 스택의 마지막 인덱스 가격(1)보다 크므로 stack.append(1) 수행
   • 스택 상태: [0, 1]
3. 세 번째 가격 처리 (i = 2):
   • prices[2] = 3
   • 현재 가격(3)이 스택의 마지막 인덱스 가격(2)보다 크므로 stack.append(2) 수행
   • 스택 상태: [0, 1, 2]
4. 네 번째 가격 처리 (i = 3):
   • prices[3] = 2
   • 현재 가격(2)이 스택의 마지막 인덱스 가격(3)보다 작으므로 스택에서 인덱스를 꺼내고 기간을 계산
   • j = stack.pop() 수행 (j = 2)
   • answer[2] = 3 - 2 = 1
   • 스택 상태: [0, 1]
   • 현재 가격(2)이 스택의 마지막 인덱스 가격(2)와 같으므로 stack.append(3) 수행
   • 스택 상태: [0, 1, 3]
5. 다섯 번째 가격 처리 (i = 4):
   • prices[4] = 3
   • 현재 가격(3)이 스택의 마지막 인덱스 가격(2)보다 크므로 stack.append(4) 수행
   • 스택 상태: [0, 1, 3, 4]

스택에 남아 있는 인덱스 처리

• 스택에 남아 있는 인덱스들은 배열의 끝까지 가격이 떨어지지 않은 경우를 의미합니다.

1. 스택 남은 처리:
   • j = stack.pop() 수행 (j = 4)
   • answer[4] = 5 - 1 - 4 = 0
   • 스택 상태: [0, 1, 3]
2. 스택 남은 처리:
   • j = stack.pop() 수행 (j = 3)
   • answer[3] = 5 - 1 - 3 = 1
   • 스택 상태: [0, 1]
3. 스택 남은 처리:
   • j = stack.pop() 수행 (j = 1)
   • answer[1] = 5 - 1 - 1 = 3
   • 스택 상태: [0]
4. 스택 남은 처리:
   • j = stack.pop() 수행 (j = 0)
   • answer[0] = 5 - 1 - 0 = 4
   • 스택 상태: []

최종적으로 answer = [4, 3, 1, 1, 0]이 됩니다.

각 인덱스의 결과는 다음과 같습니다:

• prices[0] = 1: 이후 4초 동안 가격이 떨어지지 않습니다.
• prices[1] = 2: 이후 3초 동안 가격이 떨어지지 않습니다.
• prices[2] = 3: 이후 1초 동안 가격이 떨어지지 않습니다.
• prices[3] = 2: 이후 1초 동안 가격이 떨어지지 않습니다.
• prices[4] = 3: 이후 0초 동안 가격이 떨어지지 않습니다.

따라서 함수는 [4, 3, 1, 1, 0]을 반환합니다.

 

def solution(prices):
    n = len(prices) # 주식 가격의 길이
    answer = [0]*n  # 배열 초기화
    stack = [] # 인덱스 저장
    print("prices",prices)
    
    for i in range(n):
        print("i번째",i)
        # 현재 가격이 스택의 마지막 가격보다 낮을 경우
        while stack and prices[i] < prices[stack[-1]]:
            j = stack.pop() # 스택에서 인덱스를 꺼냄
            print("j",j)
            
            answer[j] = i-j # 남은 시간 계산
            print("answer",answer)
        
        #stack에 추가
        stack.append(i)
        print("stack",stack)
    
    #스택에 남아 있는 인덱스 - 끝까지 가격이 떨어지지 않은 경우를 의미함
    while stack:
        j = stack.pop()
        answer[j] = n-1-j
        print("answer",answer)
        
    return answer


print(solution([1, 2, 3, 2, 3]))  # 결과: [4, 3, 1, 1, 0]

 

코드 결과: