<Level 2> 주식가격 with 파이썬

문제 설명

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

제한사항

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

def solution(prices):
    length = len(prices)
    answer = [0] # 답을 뒤부터 담기
    stack = [(prices[-1], length - 1)] # 비교 대상 (값, 인덱스) 스택

    for i in range(length-2,-1,-1):
        while stack and stack[-1][0] >= prices[i]:
            stack.pop()
        if not stack :
            answer.append(length - 1 - i)
        else :
            answer.append(stack[-1][1] - i)
        stack.append((prices[i], i))
    return list(reversed(answer))

 

 - 시간복잡도를 줄여야 하므로 스택을 사용하였다.

 

 - 스택에는 비교 대상을 넣는다. 값과 그 값의 인덱스 값을 튜플의 형식으로 넣도록하였다.

 

 - 답은 역순으로 담았고, 첫 시작은 0이며, 이 때 스택에 가장 끝값을 넣게된다.

 

 - for 문을 돌며 prices를 역으로 순회한다.

 

 - 만일 스택에 담긴 가장 끝 값이 현재 값보다 크거나 같으면, 앞으로 나올 수들은 현재 값만 있어도 비교가되므로 pop을 진행한다. 예시의 [1, 2, 3, 2, 3]을 보게되면 먼저 스택에는 3과 그 인덱스가 넣어져 있다. 2부터 순회를 하는데 스택에 담긴 3보다 2가 작으므로 뒤에서나올 3이나 2는 스택의 담긴 3을 볼 필요가 없을 것이다. 따라서 스택에 담겨있는 2보다 작은 3은 pop을 한다. 

 

 - 스택에 아무것도 남아 있지 않다면 끝까지 가격이 떨어지지 않는 것이므로 길이에서 현재 인덱스를 빼면 답이다.

 

 - 그 후 스택에 현재 값과 인덱스를 저장하고 반복한다.

 

 - 위의 경우에서 이어서 생각하면 2다음으로 3이오는데 이는 스택의 끝 값인 2보다 크므로 pop은 진행되지 않고 스택의 2인덱스와의 차이가 답이다. 그리고 3은 스택에 쌓인다.

 

 - 다음으로 인덱스1의 2를 살펴보자. 스택의 값만 살펴보면 [2, 3] 일 것이다. 3보다 작으므로 3을 pop하고, 2와도 같으므로 pop한다. 스택에는 아무것도 남지않으므로 끝까지 가격이 떨어지지 않는다고 볼 수 있다.

 

 

 

---

 

참고

 

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