[프로그래머스]주식가격

문제 설명

주식가격들이 주어졌을 때 각 시점에 대해 연속해서 떨어지지 않는 날의 수를 구할 것.

prices의 길이가 10만이므로 시간복잡도 유의

접근

이 문제는 왜 스택을 이용하면 편할까?

문제만 읽어봤을 때 말로 풀어쓰면 다음과 같다.

1. 매 시점마다 주식가격이 올랐는지 안올랐는지 판단한다.
2. 그리고 주식가격이 올랐거나 같으면 계속 지니고 있어서 시간을 증가시켜줘야 한다.
3. 만약 떨어졌으면 떨어진 가격보다 큰 값들은 모두 제거해줘야 한다.

매 시점마다... -> 시간이 존재한다., 그리고 지니고 있어야 하므로 특정 자료구조에 담아줘야 한다.

그리고 3번을 보면 떨어진 가격을 제거해줄 때가 중요하다.

데이터를 담은 자료형에는 담겨진 순서대로 주식가격이 가격이 같거나 증가한다.

따라서 제거할 때는 역순으로 제거해주는데, 가격이 더 낮아진다면 종료해준다 하면 가격이 큰것만 제거하여 효율적이다.

즉, 최근에 들어온 값을 먼저 고려해주는 형태이므로 stack이 적절하다.

얼마나 떨어지지 않았는지 계산할 때 어떻게 해주는게 좋을까?

index 순서대로 주식가격을 고려하므로 index가 곧 시점이 된다.

그리고 stack에 있는 주식에서 얼마나 오래 떨어지지 않았는지 계산할 때 시간을 고려해주는 변수를 추가해줘야 한다.

왜냐하면 삭제할 때 stack내 주식가격을 얼마나 보관했는지 알 수 없기 때문이다.

1. 그렇다면 stack에는 (price,지닌 시간) 형태로 들어가야할까?

   지닌 시간으로 둔다면 매 단계마다 stack에 있는 모든 원소에 대해 지닌 시간을 +1씩 해줘야 하므로 이 작업에서 시간복잡도가 증가한다.

2. (price,index)로 둔다면?

   매 단계시 단계수 - index 해주면 지닌 시간을 곧바로 알 수 있다. index는 고정된 수치이므로 더 작업해줄 것이 없다!!

   이거 말하고 싶어서 이 포스트를 쓰게 되었다.

구현

def solution(prices):
    stack = [] #element : (price, index(day))
    n = len(prices)
    answer = [0] * n
    for i in range(n):
        while stack and stack[-1][0] > prices[i]:
            price, purchaseIdx = stack.pop()
            answer[purchaseIdx] = i-purchaseIdx
        stack.append((prices[i],i))

    #마지막날 정산.
    while stack:
        prices, purchaseIdx =  stack.pop()
        answer[purchaseIdx] = i-purchaseIdx

    return answer

튜플을 넣다보니 코드 가독성이 다소 떨어졌다. 차라리 아래처럼 while을 구성하는게 나았을지도. 가독성측면에선

def solution(prices):
    stack = [] #element : (price, index(day))
    n = len(prices)
    answer = [0] * n
    for curDay in range(n):
        curStockPrice = prices[curDay]

        while stack:
            preStockPrice, preDay = stack.pop()
            #현재 값이 더 크다면 넘겨!
            if curStockPrice >= preStockPrice:
                stack.append((preStockPrice,preDay))
                break
            answer[preDay] = curDay-preDay

        stack.append((curStockPrice,curDay))

    #마지막날 정산
    while stack:
        preStockPrice, preDay = stack.pop()
        answer[preDay] = curDay-preDay

    return answer

어렵네; 뭐가 남들에게 더 보기 좋을까.