[programmers] 프로그래머스 주식가격(Python)

(주)그렙

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

(Python)

(글쓴날 : 2020.06.17)

 

---

* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 주식가격

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42584

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

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

초 단위로 기록된 주식가격이 주어질 때, 각 초의 가격을 기준으로 가격이 떨어지지 않은 기간이 몇 초인지 구하는 문제입니다.

 

저의 경우, 스택을 적용하였으며, Python을 사용했습니다.

처음에는 단순하게 2중 반복문을 써서 문제를 해결하였으나, 문제에 제시된 prices의 길이가 100,000이므로 시간 복잡도가 O(n²)인 풀이는 원래 시간 초과가 발생해야 합니다.

아마도, 테스트케이스의 범위가 작거나 연산이 단순해서 효율성 테스트를 통과한 것 같고, 문제의 의도와는 다른 풀이이므로 O(n)만에 풀기 위해 노력했으나, 결국 알아내지 못하고 다른 분들의 코드를 참조하였습니다.

이 문제의 경우, 스택을 적용하여 O(n)만에 해결이 가능하며, 직접 제출해보면 2중 반복문에 비해 훨씬 빠른 것을 알 수 있습니다.

스택 풀이법의 자세한 설명은 제가 참조했던 아래의 블로그에 자세히 되어있습니다.

 

* 참조 블로그 : https://gurumee92.tistory.com/170

---

3) 코드

 

* Python 코드

def solution(prices):
    n = len(prices)
    answer = [0] * n
    
    stack = []
    for i in range(n):
        while stack and prices[stack[-1]] > prices[i]:
            top = stack.pop()
            print(top)
            answer[top] = i - top
        
        stack.append(i)
        
    while stack:
        top = stack.pop()
        answer[top] = n - 1 - top    
        
    return answer

---