문제 파악
초 단위로 기록된 주식가격 배열 prices가 주어진다.
각 시점 i에서 가격이 떨어지지 않은 기간(초) 을 구해 배열로 반환하면 된다.
예를 들어 prices = [1, 2, 3, 2, 3] 이면,
0초(가격 1)는 이후 끝까지 한 번도 떨어지지 않으므로 4초 유지 → 4
1초(가격 2)는 2초(3)까지는 안 떨어지다가 3초(2)에서 같거나 떨어졌지만, “떨어지지 않은 기간”은 3초까지 총 3초 → 3
2초(가격 3)는 다음 초(3초)에 2로 떨어지므로 1초 → 1
3초(가격 2)는 마지막까지 유지되므로 1초 → 1
4초(가격 3)는 더 볼 시간이 없으므로 0초 → 0
정답은 [4, 3, 1, 1, 0] 이다.
처음 내 접근
prices를 큐로 접근했다.
한 칸(1초)씩 현재 값 cur를 꺼낸다.
cur과 이전에 나왔던 값들을 비교한다.
현재 값이 이전 값 이상(가격이 떨어지지 않음) 이면, 그 이전 인덱스의 유지 시간 answer[prev] += 1 을 해준다.
현재 값이 이전 값보다 작아지면(가격 하락 발생), 그 이전 인덱스는 더 이상 유지 시간이 늘지 않으므로 그 순간으로 유지 시간을 확정하고 관리 목록에서 뺀다.
이 과정을 끝까지 반복한다. 마지막에까지 한 번도 떨어지지 않은 인덱스들은 끝까지의 남은 시간을 더해주면 된다.
핵심은 “아직 떨어지지 않은 과거 시점들만 관리하면서, 새로 도착한 가격과 비교해 유지 시간을 늘리거나 종료(확정)하는 것”이다.
그런데
위의 흐름을 그대로 코드로 짜려면, 매 초마다 “아직 떨어지지 않은 과거 인덱스들”을 효율적으로 들고 있어야 한다.
여기서 큐가 아닌 스택(인덱스 저장)을 쓰면 각 인덱스가 딱 한 번 push, 최대 한 번 pop 되므로 더 효율적이다.
매 초 i의 price를 보며,
스택 맨 위 인덱스 j가 가리키는 가격 prices[j]가 현재 가격보다 크면(하락 발생), j의 유지 시간은 i - j로 즉시 확정하고 pop.
그렇지 않다면(현재 가격이 크거나 같다면), 아직 하락이 아니므로 계속 유지.
현재 인덱스 i를 스택에 push해주면 된다.
끝까지 돌고 남아있는 인덱스들은 끝까지 한 번도 떨어지지 않은 것이므로 n-1 - j 를 유지 시간으로 채운다.
풀이 및 해답
def solution(prices):
n = len(prices)
answer = [0] * n
stack = [] # 아직 "가격이 떨어지지 않은" 과거 시점들의 인덱스를 관리
for i, price in enumerate(prices):
# 현재 가격이 더 낮아졌다면, 떨어진 시점까지의 유지 시간을 확정한다.
while stack and prices[stack[-1]] > price: # : 현재가보다 비싼 과거 인덱스들을 전부 pop해서 그 시점들은 “하락 발생”으로 i - 인덱스로 확정
j = stack.pop()
answer[j] = i - j # j에서 i 직전까지는 안 떨어졌고, i에서 떨어짐
# 현재 가격의 인덱스 stack에 추가
stack.append(i)
# 끝까지 한 번도 안 떨어진 인덱스 j의 유지 시간을 마지막 시점까지로 채우는 것.
while stack:
j = stack.pop()
answer[j] = (n - 1) - j
return answer코드 흐름
입력: prices = [1, 2, 3, 2, 3]
초기화:
stack = [] # 아직 '하락을 만나지 않은' 과거 인덱스들
answer = [0,0,0,0,0]
n = 5
i=0, price=1
while: stack 비어있음 → 패스
push(0)
stack = [0]
answer = [0,0,0,0,0]
i=1, price=2
while: prices[0]=1 > 2 ? 아니오 → 패스
push(1)
stack = [0,1]
answer = [0,0,0,0,0]
i=2, price=3
while: prices[1]=2 > 3 ? 아니오 → 패스
push(2)
stack = [0,1,2]
answer = [0,0,0,0,0]
i=3, price=2 ← 하락 감지 지점
while: prices[2]=3 > 2 ? 예 → pop(2); answer[2] = 3 - 2 = 1
(다시) prices[1]=2 > 2 ? 아니오(같음은 하락 아님)
push(3)
stack = [0,1,3]
answer = [0,0,1,0,0]
i=4, price=3
while: prices[3]=2 > 3 ? 아니오
push(4)
stack = [0,1,3,4]
answer = [0,0,1,0,0]
루프 종료 후 마무리 확정(끝까지 안 떨어진 인덱스들):
pop(4) → answer[4] = (n-1) - 4 = 0
pop(3) → answer[3] = (n-1) - 3 = 1
pop(1) → answer[1] = (n-1) - 1 = 3
pop(0) → answer[0] = (n-1) - 0 = 4
최종:
answer = [4, 3, 1, 1, 0]
무심코 자료구조중 큐가 편해서 큐로 접근한 것이 별로인 선택지였다.
큐와 스택 등 해당 문제에 가장 적합한 자료구조가 무엇인지 떠올리는 습관을 가져야 할 것 같다.
