프로그래머스

프로그래머스 주식가격 풀이: 하락 시점을 찾는 단조 스택

2026년 10월 1일

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제: 주식가격
출처: 프로그래머스 코딩테스트 연습, 스택/큐
학습: 스택 자료구조 학습 가이드
자체 판단 난이도: Level 3

각 시점에서 가격이 처음 하락하는 때를 찾는다. 미래를 매번 훑으면 최악의 경우 O(n²)이 걸리므로, 아직 하락을 만나지 않은 인덱스를 단조 스택에 쌓는 관찰이 필요하다. 같은 가격은 하락이 아니라는 조건도 적용해야 하므로 Level 3으로 판단했다.

문제 원문과 제한 조건은 바뀔 수 있으니 제출 전에 공식 문제 페이지를 다시 확인한다.

1. 문제 요약

초 단위 주식 가격을 담은 prices 배열이 주어진다. 각 시점의 가격이 이후 처음으로 낮아질 때까지 몇 초 동안 유지되는지 배열로 반환한다.

가격이 끝까지 떨어지지 않으면 마지막 시점까지의 기간을 계산한다. 마지막 원소는 비교할 다음 시점이 없으므로 결과는 항상 0이다.

조건은 다음과 같다.

prices의 길이는 2 이상 100,000 이하다.
각 가격은 1 이상 10,000 이하다.
가격이 이전보다 엄격하게 낮아질 때 가격이 떨어진 것으로 봅니다.
반환 배열은 prices와 같은 길이이며, 각 위치는 해당 시점의 지속 시간입니다.

예를 들어 [1, 2, 3, 2, 3]에서 첫 가격 1은 끝까지 떨어지지 않으므로 4초 동안 유지된다. 세 번째 가격 3은 다음 초에 2로 낮아지므로 지속 시간은 1초다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

상태 전이와 경계 처리

스택에는 아직 가격이 떨어지는 시점을 만나지 못한 인덱스를 저장한다. 스택의 가격은 아래에서 위로 갈수록 작아지지 않는 순서를 유지한다.

현재 시점 i의 가격이 prices[i]일 때 스택 top의 가격보다 낮으면, top 인덱스 previous의 첫 하락 시점을 찾은 것이다.

answer[previous] = i - previous

스택 top을 꺼내고 현재 가격보다 높은 대기 가격이 남아 있는 동안 같은 처리를 반복한다. 그다음 현재 인덱스 i를 스택에 넣어 이후의 하락 시점을 기다린다.

아직 하락 시점을 찾지 못한 인덱스를 스택에서 확인한다.
현재 가격이 top 가격보다 엄격히 낮으면 해당 인덱스를 꺼내 지속 시간을 계산한다.
현재 가격 이상인 대기 가격을 만나거나 스택이 빌 때까지 반복한다.
현재 인덱스를 스택에 추가한다.
끝까지 남은 인덱스는 가격이 떨어지지 않았으므로 마지막 시점까지의 시간을 계산한다.

현재 가격이 여러 대기 시점을 한꺼번에 확정하기

각 시점마다 오른쪽 끝까지 다시 확인할 필요는 없다. 아직 답을 모르는 과거 시점을 스택에 보관하면, 현재 가격이 낮아지는 순간 해당 시점들의 답을 한꺼번에 확정할 수 있다.

예를 들어 가격이 [1, 3, 2]라면 인덱스 1의 가격 3은 인덱스 2의 가격 2를 만나는 순간 처음 하락한다. 1의 가격은 2보다 낮으므로 계속 대기 상태로 남는다. 인덱스 1의 답은 2 - 1 = 1초이고, 인덱스 0의 답은 끝까지 하락하지 않아 나중에 계산한다.

단조 스택이 중복 탐색을 없애는 이유

각 인덱스는 스택에 한 번 들어가고 첫 하락 시점에서 한 번 나온다. 스택에서 꺼내는 순간 가장 이른 하락 시점이 확정되므로 이후 가격을 다시 확인할 필요가 없다.

가격이 같을 때는 하락으로 보지 않는다. 따라서 스택에서 꺼내는 조건은 현재 가격 < top 가격인 엄격한 비교여야 한다. <=를 쓰면 같은 가격도 하락으로 잘못 판단한다.

오답 접근과 반례

각 시점에서 다음 가격부터 배열 끝까지 탐색하면 가격이 유지되거나 오르는 구간을 반복해서 확인하게 된다.

prices = [1, 2, 3, 4, 5, ...]

이 입력에서는 대부분의 시점이 끝까지 하락하지 않으므로 미래를 반복 확인하는 방식은 O(n²)까지 걸릴 수 있다. 스택을 쓰면 각 인덱스를 한 번씩만 넣고 꺼내므로 O(n)에 처리할 수 있다.

같은 가격을 하락으로 처리하지 않도록 주의해야 한다.

prices = [5, 5, 4]
기대 결과 = [2, 1, 0]

첫 번째 5는 다음 초에도 가격이 유지되므로 그때 종료하지 않고, 4로 낮아질 때까지 2초 동안 유지된다. 따라서 비교 조건은 >가 아니라 현재 가격 < 대기 가격이어야 한다.

시간·공간 복잡도

각 인덱스는 최대 한 번 push되고 한 번 pop되므로 시간 복잡도는 O(n)이다. 답 배열과 스택에는 각각 최대 n개의 원소가 저장되므로 공간 복잡도는 O(n)이다. 반환 배열은 문제에서 요구하므로 보조 스택 공간도 최악의 경우 O(n)이다.

3. 문제 해결 코드 (Python)

answer를 0으로 초기화한다. 스택에서 하락 시점이 확인된 인덱스의 답을 채우고, 끝까지 남은 인덱스는 마지막 시점까지 가격이 유지된 것으로 계산한다.

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

    for current in range(n):
        while stack and prices[current] < prices[stack[-1]]:
            previous = stack.pop()
            answer[previous] = current - previous

        stack.append(current)

    while stack:
        previous = stack.pop()
        answer[previous] = n - 1 - previous

    return answer

스택에 가격 대신 인덱스를 저장해야 현재 시점과의 차이로 지속 시간을 계산할 수 있다. 끝까지 스택에 남은 시점은 하락을 만나지 않았으므로 n - 1 - previous가 답이다. 마지막 인덱스에서는 이 값이 0이다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 공식 예제, 같은 가격, 연속 하락을 확인할 수 있다.

assert solution([1, 2, 3, 2, 3]) == [4, 3, 1, 1, 0]
assert solution([5, 5, 5]) == [2, 1, 0]
assert solution([5, 4, 3, 2]) == [1, 1, 1, 0]

4. 공식 예제와 추가 검증

작성한 solution 함수를 Python으로 실행해 공식 예제와 같은 가격·연속 하락 사례를 확인했다.

공식 예제

입력: prices = [1, 2, 3, 2, 3]
기대 출력: [4, 3, 1, 1, 0]
확인 결과: 통과
검증 목적: 오르는 구간과 중간 가격 하락을 함께 처리하는 공식 예제 확인

추가 검증 1: 모든 가격이 같은 경우

입력: prices = [5, 5, 5]
기대 출력: [2, 1, 0]
확인 결과: 통과
검증 목적: 같은 가격은 하락으로 보지 않는지 확인

추가 검증 2: 매 시점 가격이 하락하는 경우

입력: prices = [5, 4, 3, 2]
기대 출력: [1, 1, 1, 0]
확인 결과: 통과
검증 목적: 현재 가격이 여러 대기 인덱스의 답을 순서대로 확정하는지 확인

추가 검증 3: 하락 시점이 서로 다른 구간

입력: prices = [3, 3, 2, 2]
기대 출력: [2, 1, 1, 0]
확인 결과: 통과
검증 목적: 같은 가격을 유지하다가 낮아지는 시점과 끝까지 유지되는 시점을 구분하는지 확인

추가 검증 4: 길이가 긴 비하락 입력

입력: prices = [1, 2, 3, ..., 100000]
기대 출력: [99999, 99998, ..., 1, 0]
확인 결과: 통과
검증 목적: 각 시점마다 끝까지 재탐색하지 않고 선형 시간으로 처리하는지 확인

5. 다른 풀이 방식 검색 및 비교

프로그래머스 공식 문제는 각 시점 이후 처음 가격이 하락할 때까지의 지속 시간을 구하도록 정의한다.
프로그래머스 Python 풀이 그룹은 같은 문제의 공개 풀이와 접근 방식을 확인할 수 있는 공식 참고 페이지입니다.

각 시작 시점마다 뒤쪽을 순회하는 직접 탐색은 직관적이지만 최악의 경우 O(n²)입니다. 스택 풀이는 현재 값보다 큰 대기 값들을 한 번에 해결해 각 인덱스를 한 번씩만 처리한다.

비슷한 다음 값 탐색 문제인 LeetCode Daily Temperatures도 단조 스택을 사용한다. 두 문제는 답을 확정하는 비교 기준이 다르다. 주식가격은 더 낮아지는 시점을, Daily Temperatures는 더 높아지는 시점을 찾는다.

마무리

주식가격은 이후 시점을 매번 훑는 대신, 하락을 기다리는 인덱스를 단조 스택에 모아 처리한다. 현재 가격이 top보다 낮아지면 지속 시간을 확정하고, 끝까지 남은 인덱스는 마지막 시점까지 유지된 것으로 계산한다. 엄격한 하락 조건을 지키면 전체를 O(n) 시간에 처리할 수 있다.