[프로그래머스] 주식가격 (Python) - stack/deque

문제 설명

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

---

제한사항

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

---

입출력 예

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

---

먼저 해당 문제를 푼 방법은 크게 두 가지가 있다 ...

1) O(n^2) 으로 간신히 풀어버리는 방법

2) O(n)으로 효율적이게 풀어버리는 방법

 

물론 나는 1로 풀어버렸지만 2 방법으로도 풀어보고자 여러 답안을 참고해 진행해보기로 했다.

 

1) price를 돌면서, 각 가격마다 "해당 가격 이후 가격이 떨어진 순간"을 찾기 - O(n^2)

def solution(prices):
    #초기값은 끝까지 떨어지지 않았을 때를 가정하여 설정
    answer = [i for i in range(len(prices)-1,-1,-1)]
    
    for i in range(len(prices)):
        for j in range(i+1,len(prices)): #현재 price 보다 뒷 부분
            if prices[j]<prices[i]: #가격이 떨어진 순간의 초 - 현재 price의 초
                answer[i] = j-i
                break

    return answer

중요했던 것은 초기값 설정이었다.

끝까지 떨어지지 않았을 때 몇 초인지를 초기값으로 설정해야

가격이 떨어지지 않았을 때 초기값이 그대로 정답으로 출력된다!

 

하지만 이렇게 푸는 방법이 정답이라고..? 하는 생각 뿐이었고 ㅋㅋㅋㅋㅋ

인덱스 값을 사용해 효율적이게 푸는 방법이 있다고 해서 답안을 참고해 다시 풀어보기로 했다

 

 

2. price를 도는 게 아니라, "아직 답이 나오지 않은(아직 값이 떨어지지 않은) idx의 리스트"를 이용하는 방법

from collections import deque

def solution(prices):    
    #초기값은 끝까지 떨어지지 않았을 때를 가정하여 설정
    answer = [i for i in range(len(prices)-1,-1,-1)]
    
    #nodap = 아직 답을 얻지 못한 idx들 = 아직 가격이 떨어지지 않은 idx들
    #list(=stack) 사용해도 됨
    nodaps = deque([]) 
    for i in range(len(prices)):
        now = prices[i]
        
        #가격이 떨어지는 순간을 잡기 = 3 --> 2 처럼 바로 그 전의 원소와 비교하면 됨
        while nodaps and prices[nodaps[-1]] > now: 
            nodap = nodaps.pop()
            answer[nodap] = i-nodap
        
        #현재 인덱스 노답 리스트에 추가    
        nodaps.append(i)
        
    return answer

nodap 리스트 ㅋㅋㅋㅋㅋ

리스트로 사용해도 되고, deque로 사용해서 appendleft, popleft 등을 자유롭게 활용해도 된다.

 

이해하기는 훨씬 힘들었으나 거의 1/4, 1/3으로 줄어든 시간을 볼 수 있었다.

중요했던 것은, 한번 가격이 떨어지면 해당 가격에 대한 답이 나오므로 그 이후에는 해당 가격은 쳐다 볼 필요도 없다는 것 

6, 3, 4, 2 가 있다면 6에서 3으로 떨어졌을 때 6에 대한 답이 나오기 때문에 그 이후에 볼 필요도 없다.

1) 6 --> 3 에서 6에 대한 답이 나오고

2) 3 --> 4 에서는 떨어지지 않았으니 확인 할 필요가 없고

3) 4 --> 2 에서는 4와 비교해서 떨어졌으니 4에 대한 답이 나오고, 그 이후 3과 또 비교해서 3에 비해 떨어진 값이니 또 3에 대한 값이 나온다.

== 이전에 있던 6의 경우 이미 답이 나왔으므로 그냥 스택에서 빼면 된다는 것

== 4에서 2로 떨어졌을 때는 4와 3에 대해서만 떨어졌는지 확인해보면 된다는 것

 

이걸 이해를 못해서 약 30분을 고민했다...

 

이 정도면 ... 배우는 하루였다!