주식가격

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

프로그래머스

 

I. 개요

스택을 이용하여 가격이 언제 떨어졌는 지 계산하는 문제이다.

 

가격이 떨어지지 않으면 스택에 넣고, 떨어지는 시점에서 스택을 비워주면 된다.

 

 

II. 알고리즘 설계

마주할 수 있는 경우에는 실제로 떨어지거나, 한번도 떨어지지 않는 2가지 경우가 있다.

 

따라서 위 2가지의 경우를 모두 고려해야 한다.

 

1. 실제로 떨어지는 경우

스택에는 이전에 본 가격의 index들을 넣어둔다.

 

현재 보고있는 가격이 직전에 본 가격보다 작으면, 가격이 떨어지지 않은 기간을 구하고, 상승하는 과정에서 스택에 넣은 index들을 전부 빼준다.

 

가격 대신 index를 스택에 넣음으로써, 가격이 떨어지지 않은 시간을 쉽게 구할 수 있다.

 

그게 아니라면, 현재의 index를 스택에 넣어준다.

 

2. 한번도 떨어지지 않는 경우

i번째 주식이 떨어지지 않은 기간은 주어진 prices의 길이에서, i+1 만큼 뺀 값이다.

 

위의 방식으로 기간을 구하여, 답안에 반영한다.

 

 

III. 문제 풀이

1. 변수 초기화

n = len(prices)
ans = [0 for _ in range(n)]
stk = []

 

답안을 저장하기 위한 list와 스택을 만들어준다.

 

ans[i]는 i번째 가격이 떨어지지 않은 시간을 나타낸다.

 

2. 가격이 떨어질 때 까지의 시간 구하기

for i in range(n):
    while stk and prices[stk[-1]] > prices[i]:
        post = stk.pop()
        ans[post] = i - post
    else:
        stk.append(i)

 

지금 보고있는 가격보다, 이전에 본 가격이 더 높다면, 스택의 맨 위에 있는 값을 빼온다.

 

여기서 빼온 값은 가격이 내려가지 않은 시점이다.

 

이를 현재 시점(i) 에서 빼주면, 가격이 내려가지 않은 시간을 구할 수 있다.

 

가격이 내려가지 않았다면, 스택에 넣어준다.

 

 

3. 가격이 한번도 떨어지지 않은 경우

for i in stk:
    ans[i] = n - i - 1

return ans

 

스택에 남아있는 값(i)들은 한번도 가격이 내려간 적이 없다.

 

이 경우 가격이 내려가지 않은 시간은 전체 시간(n) 에서, 가격을 본 시각(i) 만큼 빼줘야 한다.

 

여기서 1을 한번더 빼주지 않으면, 정답보다 값이 1만큼 늘어나 오답으로 처리된다.

 

IV. 전체 코드

def solution(prices):
	# 1. 변수 초기화
    n = len(prices)
    ans = [0 for _ in range(n)]
    stk = []
    
    # 2. 가격이 떨어질 때 까지의 시간 구하기
    for i in range(n):
        while stk and prices[stk[-1]] > prices[i]:
            post = stk.pop()
            ans[post] = i - post
        else:
            stk.append(i)
    
    # 3. 가격이 한번도 떨어지지 않은 경우
    for i in stk:
        ans[i] = n - i - 1
    
    return ans

 

 

V. 제출 결과