스텍 / 큐 : 주식가격

문제 설명

문제 개요

주식의 가격이 초 단위로 기록된 배열이 주어질 때, 각 시점에서 "가격이 떨어지지 않은 기간"이 얼마나 되는지 구하는 문제입니다.

 

핵심 규칙

• 현재 시점부터 몇 초 후에 가격이 떨어지는가?
• 가격이 같거나 올라가는 것은 "떨어지지 않음"으로 간주
• 끝까지 떨어지지 않으면 남은 기간 전체를 반환

 

예시

prices = [1, 2, 3, 2, 3]
결과 = [4, 3, 1, 1, 0]

 

해석:

• 인덱스 0 (가격=1): 끝까지 떨어지지 않음 → 4초
• 인덱스 1 (가격=2): 끝까지 떨어지지 않음 → 3초
• 인덱스 2 (가격=3): 인덱스 3에서 2로 떨어짐 → 1초
• 인덱스 3 (가격=2): 끝까지 떨어지지 않음 → 1초
• 인덱스 4 (가격=3): 마지막 → 0초

---

문제 이해와 접근 방법

핵심 아이디어

"역방향 사고": 각 시점에서 미래를 예측하는 게 아니라, 새로운 가격이 나타날 때 이전 가격들에게 영향을 주는 방식으로 생각하기

 

최초 접근 - 큐(Queue) 사용

Queue<int[]> queue = new LinkedList<>(); // [가격, 인덱스] 저장

 

아이디어:

• 큐에 {가격, 인덱스} 형태로 저장
• 새로운 가격이 들어올 때마다 큐 앞쪽부터 확인
• 현재 가격보다 큰 이전 가격들은 "드디어 떨어짐" → 답 확정

---

큐 방식의 문제점과 해결과정

❌ 큐 방식 코드 (실패)

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n];
        
        Queue<int[]> queue = new LinkedList<>(); // [가격, 인덱스]
        
        for (int i = 0; i < n; i++) {
            // 현재 가격보다 큰 이전 가격들 처리
            while (!queue.isEmpty() && queue.peek()[0] > prices[i]) {
                int[] prev = queue.poll();
                answer[prev[1]] = i - prev[1];
            }
            
            queue.offer(new int[]{prices[i], i});
        }
        
        // 큐에 남은 것들은 끝까지 떨어지지 않은 것들
        while (!queue.isEmpty()) {
            int[] remaining = queue.poll();
            answer[remaining[1]] = n - 1 - remaining[1];
        }
        
        return answer;
    }
}

 

큐의 치명적 문제점

문제 상황:

queue = [{1,0}, {2,1}, {3,2}, {4,3}]
현재 가격 = 1

 

큐 동작 (FIFO):

1. queue.peek() → {1,0} 확인
2. 1 > 1? NO → while문 종료
3. {2,1}, {3,2}, {4,3}은 확인조차 못함!

핵심 문제: 큐는 앞에서부터만 확인하므로, 중간에 조건을 만족하지 않는 원소가 있으면 뒤의 원소들을 확인할 수 없음

 

문제 발견 과정

테스트 결과: [4,3,2,1,0] (실행값)
기댓값:     [4,3,1,1,0]

인덱스 2번에서 차이:

• 기댓값: 1 (올바름)
• 실행값: 2 (틀림)

→ 큐의 순차 접근 방식으로는 올바른 비교가 불가능함을 발견!

---

스택 방식으로 해결

스택을 선택한 이유

1. LIFO 구조: 가장 최근 원소부터 확인 가능
2. 역순 처리: 뒤에서부터 차례대로 비교
3. 중간 건너뛰기 없음: 조건을 만족하는 모든 원소 처리 가능

 

스택 방식 코드 (성공)

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n];
        
        Stack<Integer> stack = new Stack<>(); // 인덱스만 저장
        
        for (int i = 0; i < n; i++) {
            // 현재 가격보다 큰 이전 가격들 처리 (뒤에서부터!)
            while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
                int index = stack.pop();
                answer[index] = i - index;
            }
            
            stack.push(i); // 현재 인덱스 추가
        }
        
        // 스택에 남은 것들은 끝까지 떨어지지 않은 것들
        while (!stack.isEmpty()) {
            int index = stack.pop();
            answer[index] = n - 1 - index;
        }
        
        return answer;
    }
}

 

스택 방식 상세 분석

자료구조 개선

Stack<Integer> stack = new Stack<>(); // 인덱스만 저장

• 최적화: {가격, 인덱스} 대신 인덱스만 저장
• 접근: prices[index]로 가격 참조

 

핵심 로직

while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
    int index = stack.pop();
    answer[index] = i - index;
}

 

동작 과정:

1. stack.peek(): 가장 최근 인덱스 확인
2. prices[stack.peek()] > prices[i]: 가격 비교
3. 조건 만족: 가격이 떨어진 시점 발견! → 기간 계산
4. 연속 처리: while문으로 조건 만족하는 모든 원소 처리

 

시뮬레이션 예시

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

i=0: stack=[0]
i=1: stack=[0,1] (1 ≤ 2)
i=2: stack=[0,1,2] (2 ≤ 3)
i=3: prices[2]=3 > 2 → answer[2]=3-2=1, stack=[0,1,3]
i=4: stack=[0,1,3,4] (2 ≤ 3)

마지막 처리:
answer[4] = 5-1-4 = 0
answer[3] = 5-1-3 = 1  
answer[1] = 5-1-1 = 3
answer[0] = 5-1-0 = 4

결과: [4,3,1,1,0] ✓

---

큐 vs 스택 비교 정리

큐 방식의 한계

• 순차 접근: 앞에서부터만 확인 가능
• 중간 차단: 조건 불만족 시 뒤의 원소들 무시
• 비효율적: 올바른 결과 도출 불가능

스택 방식의 장점

• 역순 접근: 최근 원소부터 확인
• 연속 처리: 조건 만족하는 모든 원소 처리
• 효율성: O(n) 시간복잡도로 정확한 해결

 

핵심 교훈

자료구조 선택의 중요성: 같은 로직이라도 자료구조에 따라 결과가 달라질 수 있음. 문제의 특성을 정확히 파악하고 적절한 자료구조를 선택하는 것이 핵심!

 

시간복잡도

• O(n): 각 원소가 최대 한 번씩 스택에 들어갔다 나옴
• 공간복잡도: O(n): 최악의 경우 모든 인덱스가 스택에 저장