문제 설명
초 단위로 기록된 주식가격이 담긴 배열 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초간 가격이 떨어지지 않았습니다.
내 풀이
def solution(prices): answer = [] for i in range(len(prices) - 1): cnt = 0 for j in range(i+1, len(prices)): cnt += 1 if prices[i] > prices[j]: break answer.append(cnt) answer.append(0) return answer
문제 풀이는 비교적 단순하다.
for문을 통해 prices의 각 요소(i)가 몇 초동안 가격이 떨어지지 않는지를 구하면 된다.
for문이 돌 때마다(i가 증가할 때마다) cnt를 0으로 초기화 시켜주고 이중 for문을 통해 i부터 len(prices)-1까지 순서대로 돌며 cnt에 1을 더한다.
만약 prices[i]가 prices[j]보다 크다면, 즉 가격이 증가하는 순간 안쪽 for문을 벗어나고 answer에 cnt을 append한다.
이 때 prices의 마지막 요소에 대한 answer값은 구하지 않았지만 맨 마지막 값은 0인 것을 알고 있으므로 마지막에 따로 0을 append 해준다.
효율성 테스트: ~124.34ms / 19.5MB
다른 풀이
def solution(p): ans = [0] * len(p) stack = [0] # 결정이 안 된 요소의 인자 번호들 for i in range(1, len(p)): if p[i] < p[stack[-1]]: # 감소가 일어났을 때 for j in stack[::-1]: if p[i] < p[j]: ans[j] = i-j # ans 값을 결정 stack.remove(j) # 결정된 값은 stack에서 제거 else: break stack.append(i) for i in range(0, len(stack)-1): ans[stack[i]] = len(p) - stack[i] - 1 return ans
내 풀이는 시간 복잡도가 O(N^2)이다.
이보다 좋은 풀이를 찾기 위해 다른 풀이를 참고했다.
stack은 가격이 떨어지지 않은 기간이 결정되지 않은 요소의 인자번호를 담고 있는 리스트이고 인자는 순서대로 담기기 때문에 오름차순이다.
또한, 리스트 안에 있는 인자가 커질 수록 prices도 따라 커진다는 것을 알아두자.
기본적인 로직은 prices를 순서대로 살피면서 값이 감소한(if p[i] < p[stack[-1]]) 시점(i)에서 결과값이 확정되지 않은 시점(j)을 역순(stack[::-1])으로 탐색한다.
만약 탐색하는 시점보다 값이 감소한 시점의 가격이 작다면 i-j라는 시간만에 가격이 떨어진 것이므로 가격이 떨어지지 않은 기간을 i-j로 확정지어 ans에 입력한다.
그리고 확정된 j는 stack에서 지워준다.
else문의 의미는 p[i] >= p[j]인지를 묻는 것인데, 만약 그렇다면 아직 해당 j에 대해서는 확정을 지을 수 없으므로 break한다.
그리고 i또한 이후에 감소가 일어나는 지점을 아직은 알 수 없으므로 stack에 append한다.
for문을 다 돌고 나서도 stack에 존재하는 index 값들에 대해서는 주식가격이 끝까지 떨어지지 않았다는 것을 알 수 있다.
따라서 이들은 for문을 이용해 stack에 존재하는 index에 대하여 ans[index]에 len(p)-index-1 값을 입력해준다.
효율성 테스트: ~52.45ms / 19.6MB
내 풀이와 효율성 테스트를 비교해 봤을 때 시간이 2배 이상 절약되는 것을 알 수 있다.
