주식가격 (lv2)

문제 설명

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

제한 사항

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

---

 참 멀리 돌아서 온 문제이다. 주식의 특정 시점의 가격이 얼만큼 오래동안 그 가격보다 떨어지지 않는지 알아내는 것이 핵심임을 기억하고 다음 차트를 살펴보자.

  위 차트는 예시로 나온 주식 가격 추이를 나타낸 것이다. 시간이 지날 때 마다 그 이전에 기록된 가격들 중 현재 가격보다 낮은 가격들은 카운트를 그만해야 하는데, 이 아이디어 까지는 떠올리는데 성공했으나 그것을 구현하는데 있어 쓸데없는 짓을 하고 말았다...

 우선 문제의 의도 대로 스택으로 접근해서 문제를 살펴보자. 이 방법은 그저 위에서 떠올린 아이디어를 그대로 가져온 것이며, 반복문을 돌며 스택에 계속해서 각 시점을 넣어주고 동시에 그 스택 안에서 현재 시점의 가격보다 같거나 큰 시점들은 전부 꺼내주는 것이다. 이 방법을 처음에 떠올리지 않은것은 아니지만, 나는 그만 "가격이 하락하는 순간"에만 현재 시점과 그 동안의 주식 가격 비교를 해야한다는 착각을 하고야 말았다. 아무튼 따라서 코드는 다음과 같다...

[프로그래머스] 스택/큐 - 주식가격 (Python 풀이) (tistory.com)

[프로그래머스] 스택/큐 - 주식가격 (Python 풀이)

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

 매 시점마다, 그 이전 시점의 가격들이 현 시점 가격보다 같거나 높으면 카운트를 그만둔다는 직관적이고 효율적인 풀이이다. 같은 아이디어로 upper bound를 통해 좀 더 귀찮고 힘들게 (?) 접근할 수 있다. 반복문으로 주어진 prices를 돌면서, 어떤 리스트를 만들어 놓고 그곳에는 현 시점보다 가격이 같거나 낮은 시점들만 남겨놓는것이다.

li = []

def upperBound(target,start,end):
    while start <= end:
        mid = (start+end) // 2
        if li[mid][1] <= target:
            start = mid + 1
        else:
            end = mid - 1
    return start

def solution(prices):
    global li
    li.append((0,prices[0]))
    n = len(prices)
    answer = [0]*n
    for i in range(1,n-1):
        idx = upperBound(prices[i],0,len(li)-1)
        if idx != len(li):
            for elem in li[idx:]:
                answer[elem[0]] = i-elem[0]
            li = li[:idx]
        li.append((i,prices[i]))
    for i,v in li:
        answer[i] = (n-1) - i
    return answer