프로그래머스 Lv.2 | Python | 주식가격

1. 문제 정보

프로그래머스

• 난이도: Lv.2

---

2. 문제 설명

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

 

제한 조건

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

---

3. 접근 기준

이 문제는 단순 반복문으로 풀면 이중 반복이 되어 비효율적이다.

핵심은 다음이다.

• 현재 가격보다 더 낮은 가격이 처음 등장하는 시점을 찾아야 한다.
• 그 시점까지의 시간 차이를 계산한다.

“가격이 떨어지는 순간을 빠르게 찾는 구조”가 필요하다.

---

4. 사용한 패턴 / 알고리즘

스택 (Stack)

• 아직 가격이 떨어지지 않은 인덱스를 저장
• 가격이 떨어지는 순간 한 번에 처리

---

5. 핵심 아이디어

스택에는 “아직 가격이 유지되고 있는 시점의 인덱스”를 넣는다.

현재 가격이 이전 가격보다 낮아지는 순간:

• 스택에서 꺼내면서 떨어진 시점을 계산한다.
• 가격 상승/유지 → 스택에 계속 쌓음
• 가격 하락 → 스택에서 꺼내면서 answer 리스트에 유지 시간을 저장

---

6. 풀이 코드

def solution(prices):
    n = len(prices)
    answer = [0] * n  # 각 시점의 유지 시간
    stack = []  # 아직 가격이 떨어지지 않은 인덱스 저장

    for i in range(n):
        # 현재 가격이 이전보다 낮아지는 순간
        while stack and prices[stack[-1]] > prices[i]:
            # 가격이 떨어진 시점 처리
            idx = stack.pop()
            answer[idx] = i - idx  # 떨어지기까지 걸린 시간
        
        # 아직 떨어지지 않았으므로 스택에 추가
        stack.append(i)

    # 끝까지 가격이 떨어지지 않은 경우 처리
    while stack:
        idx = stack.pop()
        answer[idx] = n - 1 - idx  # 끝까지 유지된 시간

    return answer

---

7. 동작 흐름 예시

예:

prices = [1, 2, 3, 2, 3]

 

진행 과정

i=0 → stack=[0]

i=1 → stack=[0,1]

i=2 → stack=[0,1,2]

i=3 (가격 2)
→ 3 > 2 → pop(2) → answer[2] = 1
→ stack=[0,1]

i=4 → stack=[0,1,3,4]

 

마지막 처리

남은 스택: [0,1,3,4]

answer[4] = 0
answer[3] = 1
answer[1] = 3
answer[0] = 4

 

결과:

[4, 3, 1, 1, 0]

 

---

8. 핵심 로직 요약

이 문제의 핵심은 가격이 떨어지는 순간을 기준으로 이전 시점을 한 번에 처리하는 것이다.

• 스택에 인덱스를 저장한다.
• 현재 가격이 더 낮아지면:
  • 스택에서 꺼내면서 유지 시간 계산
• 끝까지 떨어지지 않은 값은 마지막에 처리

“스택으로 유지 상태 관리 + 하락 시 한 번에 처리”

---

9. 마치며

처음 보면 그냥 “언제 떨어지는지 찾으면 되겠네”라고 생각해서 이중 반복문으로 접근하기 쉽다.

그런데 그렇게 풀면 바로 비효율이 된다.

이 문제를 풀면서 중요한 포인트는 하나였다.

• “떨어지는 순간에 과거를 처리한다”

이걸 못 떠올리면 계속 하나씩 비교하게 되고, 이걸 떠올리면 스택으로 한 번에 정리된다.

결국 이 문제는 미래를 보면서 현재를 처리하는 게 아니라, 현재를 보면서 과거를 정리하는 문제라는 느낌이 강하다.