[코딩테스트] 프로그래머스 - 주식 가격 (Lv.2) in Python

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return

 

예시:

prices = [1,2,3,2,3]

return = [4,3,1,1,0]

 

 

programmers.co.kr/learn/courses/30/lessons/42584

 

풀이

주어진 배열을 차례대로 살펴보고, 조건에 따라 바로 전 값부터 살펴보는 문제임에 스택이 적절하겠다는 생각이 들었다!

 

다만 어떤 값을 스택에 저장하느냐에서 많이 애를 먹었는데... ㅜ

결론은 주식의 값이 아니라, 해당 시간을 저장하는 것이 답이었다.

 

예시:

stack = []

answer = []

prices = [1      2     3    1     3]

            0초  1초  2초  3초  4초

 

라고 하자.

 

0초일 때

비교대상이 없으므로, stack에 현재 시간 (0)을 append.

stack = [0]

 

1초일 때

비교대상이 있으므로, 주식 가격이 떨어졌는 지 확인

스택의 끝에 저장되어 있는 시간대의 가격이,

현재 시간 주식 가격과의 비교 대상이다.

stack[-1] = 0

prices[0] = 1 //비교 대상

prices[1] = 2 //현재 가격

 

~> 가격이 떨어지지 않았으므로, 현재 시간을 stack에 푸시.

stack = [0, 1]

 

2초일 때

stack[-1] = 1

prices[1] = 2

prices[2] = 3

~> 가격이 떨어지지 않았으므로, 현재 시간을 stack에 푸시.

stack = [0,1,2]

 

3초일 때

stack[-1] = 2

prices[2] = 3

prices[3] = 1

~> 가격이 떨어졌으므로, 유지시간을 구해준다.

3 (현재 시간) - 2 (스택의 마지막에 저장된 시간) = 1초

 

2초일 떄의 가격이 1초동안 유지된 것이므로,

answer[stack[-1]] = answer[2] = 1

로 설정.

2초일 때 가격의 유지시간은 이미 구했으므로, stack에 계숙 둘 필요가 없다.

따라서 pop해줌.

stack = [0,1]

 

또다시 스택의 마지막 시간대 가격과 비교를 해주자.

stack[-1] = 1

prices[1] = 2

prices[3] = 1

~> 가격이 떨어졌으므로, 유지시간을 구해준다.

3 (현재 시간) - 1 (스택의 마지막에 저장된 시간) = 2초

answer[1] = 2

stack = [0]

 

또한, 현재 시간의 가격이 얼마나 유지되는 지 계속 비교해줘야 하므로,

현재 시간은 또다시 stack에 푸시해준다.

 

stack = [0,3]

 

4초일 때

stack[-1] = 3

stack[3] = 2

stack[4] = 3

~> 가격이 떨어지지 않았으므로, 스택에 현재 시간 푸시

stack = [0,3,4]

 

 

=> 이제 prices 배열의 모든 원소 탐색이 끝났다.

스택에 들어있는 시간을 봤을 때,

 

마지막 시간 - 스택 안 시간 = 가격이 떨어지지 않은 시간 임을 알 수 있다!

 

따라서

answer[4] = 4 (마지막 시간) - 4 = 0

answer[3] = 4 - 3 = 1

answer[0] = 4 - 4 = 0

 

이렇게 구하면 됨.

 

파이썬 풀이

 

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