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

문제 보기

이 문제는 스택/큐 문제이다.

주식이 시간이 지남에 따라 가격이 떨어지지 않은 시간이 얼마인지 구하는 문제이다.

현재 시간에서 미래에 가격이 떨어지는 시간까지 탐색을 해야하기 때문에 O(n^2)이 나올거라고 생각했다.

 

문제를 푼 로직은 다음과 같다.

1. 각 시간에서의 주식 가격에 대해서 (5~6번째 줄)
2. 주식 가격이 떨어지지 않는 시간을 구한다. (8~15번째 줄)
3. 각 시점에서의 주식 가격이 떨어지지 않는 시간을 업데이트한다. (17번째 줄)

 

여기서 눈여겨 볼 점은, 11~15번째 줄이다. 먼저 시간부터 센 다음, 만약 주식 가격이 떨어지면 break를 통해 반복문을 벗어난다.

이는 예제 입력을 보면 알 수 있다.

주식 가격이 상승을 하던 하락을 하던 일단 1초는 지나가기 때문에 시간을 먼저 세는 것이다.

 

def solution(prices):
	answer = [0 for _ in range(len(prices))]
	length = len(prices)
	
	# for all stock prices
	for i, p in enumerate(prices):
		
		# estimate duration
		duration = 0
		for j in range(i + 1, length, 1):
			# count time unconditionally
			duration += 1
			# if a stock price drops
			if prices[j] < p:
				break
		
		answer[i] = duration
		
	return answer