[programmers] 프로그래머스 주식가격(Python)
[programmers] 프로그래머스 주식가격
(Python)
(글쓴날 : 2020.06.17)
* programmers, 프로그래머스 문제 Python 언어 풀이입니다.
* 소스 코드의 저작권은 글쓴이에게 있습니다.
프로그래머스 주식가격
1) 문제
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42584
코딩테스트 연습 - 주식가격
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00
programmers.co.kr
2) 풀이 과정
* 시간 복잡도 : O(n)
초 단위로 기록된 주식가격이 주어질 때, 각 초의 가격을 기준으로 가격이 떨어지지 않은 기간이 몇 초인지 구하는 문제입니다.
저의 경우, 스택을 적용하였으며, Python을 사용했습니다.
처음에는 단순하게 2중 반복문을 써서 문제를 해결하였으나, 문제에 제시된 prices의 길이가 100,000이므로 시간 복잡도가 O(n²)인 풀이는 원래 시간 초과가 발생해야 합니다.
아마도, 테스트케이스의 범위가 작거나 연산이 단순해서 효율성 테스트를 통과한 것 같고, 문제의 의도와는 다른 풀이이므로 O(n)만에 풀기 위해 노력했으나, 결국 알아내지 못하고 다른 분들의 코드를 참조하였습니다.
이 문제의 경우, 스택을 적용하여 O(n)만에 해결이 가능하며, 직접 제출해보면 2중 반복문에 비해 훨씬 빠른 것을 알 수 있습니다.
스택 풀이법의 자세한 설명은 제가 참조했던 아래의 블로그에 자세히 되어있습니다.
* 참조 블로그 : https://gurumee92.tistory.com/170
3) 코드
* Python 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
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
|