코딩테스트
[프로그래머스] 주식가격 | 스택/큐
Michelle Kim
2023. 5. 15. 00:22
from collections import deque
def solution(prices):
answer = []
prices = deque(prices)
while prices:
#print(answer)
value = prices.popleft()
length = len(prices)
for idx, price in enumerate(prices):
if price < value:
answer.append(idx+1)
break
else:
answer.append(length)
return answerTROUBLE SHOOTING: 처음에 모든 테스트 케이스를 다 통과했으나 nested loop (While 안의 for문) 때문에 시간복잡도가 O(n^2) 되어서 효율성에서 하나도 통과를 못한줄 알았다.
그런데 알고보니, 문제는 deque 를 사용하지 않고 그냥 list.pop(0)을 사용했기 때문이었다.
chatgpt 에 의하면
The time complexity of popleft() is O(1), which means it is a constant time operation regardless of the size of the deque.
The time complexity of pop(0) is O(n), where n is the length of the list, because all the remaining elements in the list have to be shifted one position to the left after the first element is removed.
단순하게 답은 pop(0) 에서 popleft()로 바꿨는데 해결이 되었다.
풀이:
Step1. 일단 popleft 를 사용하려면 deque 를 import 해주어야한다
Step2. 첫번째 값을 pop 해주고 나머지 리스트에서 그 값보다 작은 값이 있는지 확인해준다
Step3. 만약 더 작은 값이 있으면 그 index+1 값 (= 몇초간 떨어지지 않았는지)를 answer 에 저장.
for 문이 끝났는데 더 작은 값이 없으면 else 문이 실행되서 나머지 리스트의 길이(= 몇초간 떨어지지 않았는지 전체)를 answer 에 저장
Step4. answer 리턴
찾아보니, 나처럼 queue 로 풀었을때 말고 스택으로 효율적인 코드를 짠 분도 계셨다!
def solution(prices):
length = len(prices)
# prices 리스트가 모든 시간을 버텼을때 (max) 값으로 채워주기
# ex. 리스트길이가 3이면 => [2,1,0], 4이면 => [3,2,1,0]
answer = [ i for i in range (length - 1, -1, -1)]
stack = [0] # stack 은 항상 answer 리스트, prices 비교대상의 idx 값을 갖고 있음
for i in range (1, length): # 1~n-1까지 prices 순회
while stack and prices[stack[-1]] > prices[i]:
j = stack.pop()
answer[j] = i - j
stack.append(i) #다음 answer 리스트 idx 값 업데이트 (+=1)
return answer