문제

주식가격

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

---

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

---

입출력 예시

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

---

문제 풀이

1초	2초	3초	4초	5초	떨어지지 않은 기간
1원	O	O	O	O	4초
	2원	O	O	O	3초
		3원	X		1초
			2원	O	1초
				3원	0초

떨어지지 않은 기간을 보면
초끼리 빼면 나오지 않을까하는 생각이 든다.

예를 들어 1초의 1원은 끝까지 떨어지지 않았으므로 5 - 1인 4초,
3초의 3원은 4초에서 떨어지기 때문에 4 - 3인 1초
5초의 3원은 5초에서 끝나기 때문에 5 - 5인 0초

이런 식으로 초를 스택에 쌓고 돌리면 될 것 같은 느낌적인 느낌..

1초

1초에는 초 스택에 아무것도 없으므로 초 추가

초
1

2초

2초에는 2원이 되므로
스택에 쌓여 있는 초의 금액과 비교해봤을 때
1초에는 1원, 2초에는 2원이므로 가격이 떨어지지 않았음.
따라서 초 스택에 2초 추가

초
2
1

3초

3초에는 3원이 되므로
스택에 쌓여 있는 초 중 제일 위의 금액이랑 우선 비교해봤을 때
2초에는 2원, 3초에는 3원이므로 가격이 떨어지지 않았음.
따라서 초 스택에 3초 추가

초
3
2
1

4초

4초에는 2원이 되므로
스택에 쌓여 있는 초 중 제일 위의 금액이랑 우선 비교해봤을 때
3초에는 3원, 4초에는 2원이므로 가격이 떨어졌다.
이때 초 스택에서 3초를 빼고 4 - 3인 1초를 결과 배열에 집어넣는다.

1초	2초	3초	4초	5초
0	0	1	0	0

초
2
1

그리고 다시 2초의 2원과 4초의 2원을 비교한다.
떨어지지 않았으므로 4초를 초 스택에 넣는다.

초
4
2
1

5초

5초에는 3원이 되므로
스택에 쌓여 있는 초 중 제일 위의 금액이랑 우선 비교해봤을 때
4초에는 2원, 5초에는 3원이므로 가격이 떨어지지 않았음.
따라서 초 스택에 5초 추가

초
5
4
2
1

전부 끝내고 나서 초 스택이 비어있지 않기 때문에
전체 초 길이에서 스택에서 뽑아낸 초를 빼면 해당 초의 가격이 떨어지지 않은 기간을 알 수 있다.

전체 초 길이는 5이고 초를 빼면

5 - 5 = 0
5 - 4 = 1
5 - 2 = 3
5 - 1 = 4

총 결과 배열은 다음과 같다.

1초	2초	3초	4초	5초
4	3	1	1	0

def solution(prices):
    length = len(prices)
    answer = [0] * length
    stack = []

    for i in range(length):
        # 스택이 비어있지 않고 가격이 떨어진 경우
        while stack and prices[stack[-1]] > prices[i]:
            # 이전 시간
            past_idx = stack.pop()

            # 가격이 떨어졌으면 현재 초와 이전 시간 간의 차이가 가격이 떨어지지 않은 기간임을 나타낸다.
            answer[past_idx] = i - past_idx

        # 가격이 떨어지지 않은 경우 시간 스택에 추가한다.
        stack.append(i)

    # 다 끝내고 남은 주식들의 기간을 체크한다.
    while stack:
        past_idx = stack.pop()

        # 인덱스는 0부터 시작이므로 전체 시간에 - 1 해서 맞춰야 한다.
        answer[past_idx] = length - 1 - past_idx

    return answer