Programmers Coding Quiz #31 주식가격(FAIL)
문제 설명
초 단위로 기록된 주식가격이 담긴 배열 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):
result = []
for i, x in enumerate(prices):
count = 0
for y in prices[i + 1:]:
count += 1
if x > y:
break
result.append(count)
return result
- x를 x이후로로 부터 정렬된 리스트로 비교하면 되므로 enumerate를 통해 얻은 인덱스로 슬라이싱한 리스트를 순회하며 비교합니다.
- count를 계속 더해주되, x가 y보다 작아진 시점에선 break로 for문을 중지하고 그 시점까지 쌓인 count를 result에 넣고, 아닌 경우 끝까지 순회에 쌓인 count를 넣어주면 됩니다.
비교적 단순하게 풀긴 했지만 결론적으로 이 풀이는 실패했습니다. 시간 복잡도에서 이중 for문은 O(N^2)의 형태를 가지게 됩니다. 다른 분들 중에 이중 for문을 쓰고도 풀어낸분이 있지만 문제의 취지에는 맞지않습니다. 이 문제는 스택과 큐를 활용해야 합니다.
(range를 활용한 이중 for문과 enumerate를 쓴 이중 for문의 차이는 enumerate는 반복자료형 원소를 하나하나 체크해야되지만, range는 그럴필요가 없이 O(1)이기 때문에 실행시간의 차이가 발생하게 됩니다.)
다른풀이
def solution(prices):
n = len(prices)
# 1. answer를 prices 길이와 맞춘다.
answer = [0] * n
# 2. 스택 생성
st = []
# 3. 0 ~ n-1 초까지 순회
for i in range(n):
# 1. 스택 비지 않고, prices[top] > prices[i] 이라면 다음 반복
# 1-1. 스택에서 마지막에 저장된 시간 top 꺼냄
# 1-2. answer[top]에 i - top을 저장
while st and prices[st[-1]] > prices[i]:
top = st.pop()
answer[top] = i - top
# 2. 스택에 현재 시간 i 저장
st.append(i)
# 4. 만약 스택이 남아있다면, 스택이 빌 때까지 다음 반복
while st:
# 1. 스택에서 마지막에 저장된 시간 top 꺼냄
# 2. answer[top]에 가장 마지막 시간 n - i 에서 top을 뺸 시간 저장
top = st.pop()
answer[top] = n - 1 - top
return answer
from collections import deque
def solution(prices):
answer = []
prices = deque(prices)
while prices:
c = prices.popleft()
count = 0
for i in prices:
if c > i:
count += 1
break
count += 1
answer.append(count)
return answer
Author And Source
이 문제에 관하여(Programmers Coding Quiz #31 주식가격(FAIL)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@keywookim/Programmers-Coding-Quiz-31-주식가격FAIL저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)