[스택큐] 주식 가격 - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/42584

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

본 문제는 각 price 정보마다 해당 price가 언제 감소하는 지까지의 기간을 초 단위로 count하여 리스트에 저장하는 문제

 

굉장히 효율성을 고려하지 않을 때 코드는 다음과 같다.

물론 해당 코드도 비교적 쉽게 통과가 되었다.

최악의 경우 O(n^2) 정도의 알고리즘이 된다.

 

하지만 효율성 부분이 115ms 정도가 나오는 것은 그다지 좋은 코드가 되지 못하다.

 

nlogn 이내로 통과하는 알고리즘을 구현해보도록 하자

 

여기서 상기해야할 게 이 문제가 stack queue 파트라는 거다. 어느 부분에 스택 큐 자료구조가 사용될까?

 

collction 패키지에 내장되어 있는 deque 패키지를 사용해보자

 

따로 queue를 파이썬으로 구현하는 연습도 해보자

 

 

이 문제를 스택으로 푸신 분 구현한 것도 공부하자

https://deftkang.tistory.com/175

[알고리즘]주식가격(프로그래머스 문제) python 풀이(스택)

def solution(prices) : 
	answer = [0]*len(prices)
	stack = []
	
	for i, price in enumerate(prices) : 
		# stack이 비었으면 false
		while stack and price < prices[stack[-1]] : 
			j = stack.pop()
			answer[j] = i - j
		stack.append(i)
	# for문 다 돌고 stack에 남아있는 것들 pop
	while stack : 
		j = stack.pop()
		answer[j] = len(prices) - 1 - j
	return answer