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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 주식의 가격이 떨어지면 몇 초 뒤에 가격이 떨어졌는지를 기록해 return하는 문제다.

만약 가격이 떨어지지 않았다면, 끝났을 시간을 고려해 return 하면 된다.

 

2중 for문으로 비교하면 O(n^2)의 시간복잡도를 갖기 때문에 시간 초과가 걸리게 될 것이다.

그러므로 다른 방법으로 풀어야 하는데, stack 구조를 이용하면 쉽게 풀 수 있다.

 

항상 stack의 맨 위에 어떤 주식 가격이 가장 높은 시간을 둔다.

만약 stack의 맨 위에 있는 주식보다 가격이 낮다면, 가격이 떨어지는 순간이므로 시간을 계산해 answer에 저장한다.

 

만약 가격이 높거나 같다면, stack에 삽입한 뒤 다음 주식 가격을 보면 된다.

 

이렇게 할 경우 항상 주식 가격이 가장 높은게 stack의 맨 위에 오기 때문에 stack에 쌓인 주식들은 내림차순으로 비교가 되는 모습을 띄게 된다.

 

그러므로 stack에 있는 주식보다 작은데 비교를 하지 않는 예외가 발생하지 않아 O(n)의 시간복잡도로 문제를 해결할 수 있다.

 

 

 

 

​

[아이디어 정리]

1. stack의 맨 위에 항상 주식의 가격이 가장 높은 게 위치하도록 한다.
2. 만약 현재 주식의 가격이 stack의 맨 위에 있는 가격보다 작다면 stack의 맨 위에 있는 주식은 가격이 떨어졌으므로, 그 때 시간을 answer에 저장한다.
3. 만약 stack의 맨 위의 주식 가격이 현재 주식의 가격과 같거나 높다면 stack의 맨 위에 쌓고 다음 주식 가격과 비교한다.
4. 모든 주식의 비교가 끝나면 stack에 쌓인 주식을 꺼내서 answer을 한번 더 갱신한다. (stack에 쌓인 주식들은 가격이 떨어지지 않은 경우이므로 경과한 시간에서 처음 등장한 시간을 빼서 구하면 된다.)

 

 

 

Code

 

 

from collections import deque
def solution(prices):
    answer = [0]*len(prices)
    dq= deque()
    i=0
    while(i<len(prices)):
        num=prices[i]
        if (len(dq)<1):
            dq.append([num,i])
        else:
            while(len(dq)>0):
                top=dq.pop();
                if (top[0]>num):
                    answer[top[1]]=i-top[1]
                else:
                    dq.append(top)
                    break
            dq.append([num,i])
        i+=1
    while(len(dq)>0):
        nums=dq.pop();
        answer[nums[1]]=len(prices)-nums[1]-1
    return answer

 

---

2중 for문을 활용한 python 풀이 말고 다른 풀이가 있냐는 질문에 답하느라 Python으로 오랜만에 풀었다

이젠 C++이 너무 익숙해...

프로그래머스