스택 - 주식가격

이번 문제는 Stack을 이용해서, 주식 각격의 변동 기간을 확인하는 문제입니다.

https://programmers.co.kr/learn/courses/30/lessons/42584?language=python3 

코딩테스트 연습 - 주식가격

해당 문제는, 1일부터 N일차까지 당일의 주식 가격이 Input으로 주어지고,

 

해당 시점부터 얼마나 가격이 안떨어지는지를 물어보는 문제입니다.

 

처음에 문제를 봤을 때, "해당 가격보다 높았던 날의 수" 인지, 아니면 "해당 가격을 유지한 날의 수"

 

인지가 문제에서 햇갈렸습니다

 

예시를 보면 이해가 쉽습니다.

ex. [6, 7, 6, 4, 1, 8, 9]

요렇게 Input값이 있을 때, 첫째날만 기준으로 본다면

6은 2일까지 가격이 유지되었고, 3일째 가격이 처음보다 떨어졌습니다.

이걸로 끝입니다!

저는 여기서, 그럼 그 이후 6보다 큰 8, 9는? 을 생각했는데

이번 문제에서는 유지된 기간만 관심을 갖습니다.

 

이때, Stack을 이용하면 복잡한 계산 없이 빠른 알고리즘 설계가 가능합니다.

 

1. N째날의 주식값을 Stack의 최상단 값과 비교한다

2. 최상단 값보다 N번째 날의 주식값이 높으면, 주식이 떨어지지 않았으므로 N번째 날의 주식값을 Stack에 저장

2_1. 최상단 값보다 N번째 날의 주식값이 낮으면, 전날보다 떨어진 것이므로 (Stack의 최상단)번째 날의 값을 Pop

      + (Stack의 최상단)번째 날의 주식이 얼마나 유지되었는지 Update

3. N이 len(prices)가 아니면, 다시 1번으로 돌아가서 반복

4. N==len(prices)에 도달하면, Stack에 남아있는 날짜는 하락한 적이 없는 것이므로, 유지기간을 Update

 

순서도였으면 차라리 편했을 것 같은데, 순서도보단 아래 코드가 보다 이해하시기 쉬울것같습니다 :)

 

def solution(prices):
    answer = [0 for i in prices]
    stack = []    
    for i in range(len(prices)):
        #stack이 비어있으면, 스택에 해당 시점을 push
        if len(stack)==0:
            stack.append([prices[i],i])
        else:
            #stack이 비지 않았을 때
            #stack의 값 중 이번 시점의 주식가격보다
            #높은 값이 있으면 pop, 아니면 계속 push를 진행합니다.
            while True:                                
                if len(stack)==0:
                    stack.append([prices[i],i])
                    break
                else:
                    if stack[-1][0]<=prices[i]:
                        stack.append([prices[i],i])
                        break
                    else:
                        temp = stack.pop()    
                        answer[temp[1]]=i-temp[1]
    #이 시점에서, 이제 pop되지 않은 주식의 시점들이 stack에 남아있으며
    #해당 시점들은 i(주식 시장 진행 날짜의 수)에서 해당 날짜마큼의 차이값동안
    #주식의 값이 유지되었다고 볼 수 있습니다.
    stack = [[j[1],i-j[1]] for j in stack]        
    #stack의 모든 값들을 빼서 answer를 최신화 시켜줍니다.
    for i in stack:
        answer[i[0]]=i[1]
    return answer