주식 가격

프로그래머스의 '주식가격' 문제는 초 단위로 기록된 주식 가격 배열을 보고, 각 가격이 떨어지지 않고 유지된 기간이 몇 초인지 계산하는 문제입니다.

이 문제는 단순하게 이중 for문으로도 풀리지만, 효율성을 고려하면 **스택(Stack)**을 사용하는 것이 정석입니다. 두 가지 방법을 모두 설명해 드릴게요.

---

1. 스택(Stack)을 이용한 효율적인 풀이

스택을 사용하면 모든 원소를 한 번씩만 훑으면서 처리할 수 있어 시간 복잡도가 $O(N)$으로 매우 효율적입니다.

Python

 

def solution(prices):
    n = len(prices)
    answer = [0] * n
    stack = []  # 가격이 떨어지지 않은 인덱스를 담는 스택

    for i in range(n):
        # 스택이 비어있지 않고, 현재 가격이 스택의 마지막 가격보다 떨어졌다면
        while stack and prices[i] < prices[stack[-1]]:
            j = stack.pop()
            answer[j] = i - j  # 떨어진 시점 - 들어온 시점 = 유지 시간
        stack.append(i)

    # 끝까지 가격이 떨어지지 않은 인덱스들 처리
    while stack:
        j = stack.pop()
        answer[j] = n - 1 - j

    return answer

2. 이중 반복문(Brute Force) 풀이

문제의 제약 조건이 아주 까다롭지 않다면 이해하기 쉬운 이중 for문으로도 통과가 가능합니다. 시간 복잡도는 $O(N^2)$입니다.

Python

 

 

def solution(prices):
    n = len(prices)
    answer = [0] * n
    
    for i in range(n):
        for j in range(i + 1, n):
            answer[i] += 1
            if prices[i] > prices[j]: # 가격이 떨어지면 중단
                break
                
    return answer

---

💡 핵심 포인트 (헷갈리기 쉬운 부분)

• **"1초 뒤에 가격이 떨어져도 1초간은 유지된 것으로 본다"**는 점이 중요합니다.
  • 예를 들어 [3, 1]에서 3은 바로 다음 초에 1로 떨어지지만, 답은 1입니다.
• 스택 방식의 원리: 가격이 계속 오르거나 같으면 스택에 인덱스를 쌓아두다가, 가격이 떨어지는 순간 스택에서 자기보다 비쌌던 애들을 다 꺼내며 "너 여기서 떨어졌어!"라고 기간을 확정 짓는 방식입니다.

이해를 돕기 위해 prices = [2, 3, 2, 1]인 상황을 가정하고 단계별로 설명해 드릴게요.

---

1. 동작 원리: "가격이 떨어질 때까지 일단 버티기"

이 코드는 주식의 값 자체가 아니라, 주식의 **위치(인덱스)**를 스택에 넣습니다. 그래야 나중에 "몇 초 동안 유지됐는지" 계산할 수 있기 때문이죠.

1단계: 가격이 오르거나 같을 때 (stack.append(i))

• prices[0]=2, prices[1]=3 순서대로 들어옵니다.
• 2초 시점(가격 3)은 1초 시점(가격 2)보다 높으므로, 가격이 떨어지지 않았습니다.
• 스택에 인덱스 [0, 1]이 차곡차곡 쌓입니다.

2단계: 가격이 떨어지는 순간 (while문 실행)

• prices[2]=2가 등장합니다. 이때 스택 맨 위(최근)에 있는 prices[1]=3보다 가격이 낮아졌죠?
• "드디어 가격이 떨어졌다!" 하고 스택에서 1을 꺼냅니다(pop).
• answer[1] = 현재시간(2) - 들어온시간(1) = 1초라고 기록합니다.

3단계: 끝까지 안 떨어진 데이터 처리

• 모든 반복문이 끝났는데도 스택에 남아있는 인덱스들은 "배열이 끝날 때까지 가격이 한 번도 안 떨어진" 경우입니다.
• 전체 길이에서 자신의 위치를 빼서 유지 시간을 계산합니다.

---

2. 코드의 핵심 로직 분석

Python

 

while stack and prices[i] < prices[stack[-1]]:
    j = stack.pop()
    answer[j] = i - j

• stack: 아직 가격이 떨어지지 않은 주식들의 '인덱스'가 들어있습니다.
• prices[i] < prices[stack[-1]]: 현재 주가(prices[i])가 스택에 마지막으로 담긴 주가(prices[stack[-1]])보다 낮아졌는지 확인합니다.
• i - j: 현재 시점(i)에서 그 주식이 들어왔던 시점(j)을 빼면, 가격이 유지된 전체 시간이 나옵니다.

---

3. 왜 이 방식이 더 빠를까? (효율성)

• 이중 for문: 모든 시점에 대해 뒤에 있는 모든 시점을 다 확인합니다 ($O(N^2)$).
• 스택: 모든 주식은 스택에 한 번 들어갔다가 한 번 나옵니다. 즉, 데이터가 10만 개라면 딱 20만 번 정도의 연산으로 끝납니다 ($O(N)$).

💡 한 줄 요약

"스택에 일단 넣어두고, 나중에 나보다 싼 값이 나타나면 그때 스택에서 꺼내며 유지 기간을 확정 짓는 방식"입니다.

이 로직을 직접 손으로 [1, 2, 3, 2, 3] 같은 예시를 그려보며 따라가면 훨씬 이해가 빠르실 거예요. 혹시 특정 줄의 코드가 왜 필요한지 더 궁금한 부분이 있으신가요?

 

1. 큐(Queue)를 이용한 직관적인 풀이

이 방법은 현재 가격을 하나 뽑고, 남은 가격들을 순서대로 확인하며 가격이 떨어질 때까지 초(second)를 세는 방식입니다.

Python

 

from collections import deque

def solution(prices):
    answer = []
    # 1. 주식 가격들을 큐(Queue)로 만듭니다.
    queue = deque(prices)
    
    # 2. 큐가 빌 때까지 하나씩 꺼내서 확인합니다.
    while queue:
        price = queue.popleft() # 현재 시점의 주가
        sec = 0 # 유지 시간 카운트
        
        # 3. 큐에 남은 뒷부분 가격들과 비교합니다.
        for next_price in queue:
            sec += 1 # 일단 1초는 지났다고 봅니다.
            if price > next_price: # 어? 가격이 떨어졌네?
                break # 더 이상 보지 않고 멈춤
        
        answer.append(sec)
        
    return answer

---

2. 왜 이 방식이 더 이해하기 쉬운가요?

이 로직은 인덱스 번호(i, j)를 관리할 필요가 없습니다.

1. popleft(): 맨 앞의 주식을 꺼냅니다. (현재 확인하려는 주식)
2. for next_price in queue: 뒤에 줄 서 있는 주식들을 하나씩 꺼내서 봅니다.
3. sec += 1: 다음 주식을 확인했다는 건 이미 1초가 흘렀다는 뜻입니다.
4. if price > next_price: 만약 다음 주식이 지금보다 낮으면, 거기서 카운트를 멈춥니다.

---

3. 알아두어야 할 점 (효율성)

• 직관성: 인덱스 계산이 없어서 코드가 매우 깔끔하고 읽기 편합니다.
• 성능: 이 풀이는 최악의 경우(가격이 계속 오르는 경우) $O(N^2)$의 시간 복잡도를 가집니다. 하지만 파이썬의 deque는 popleft() 연산이 매우 빠르기 때문에, 프로그래머스의 효율성 테스트를 통과하는 데 큰 무리가 없습니다.

---

💡 요약하자면

"앞에서부터 주식을 하나씩 뽑아서(popleft), 뒤에 남은 애들(queue)이랑 하나하나 비교해보고, 가격이 낮아지면 멈춘다!"라고 생각하시면 됩니다.

이 방식이 인덱스를 사용하는 방식보다 더 이해하기 편하신가요? 아니면 이 로직에서 특정 부분이 여전히 아리송하신가요?