[코테] 주식가격 (스택/큐)

주식가격 (스택/큐)

2026.4.5., 2026.4.12., 2026.4.13.

https://school.programmers.co.kr/learn/courses/30/lessons/42584

핵심 개념

단조 스택 (Monotonic Stack)

아직 답을 못 구한(=조건을 미충족한) 것들을 스택에 쌓아두다가, 조건이 충족되는 순간 꺼내면서 답을 계산한다

단조 - 스택 안의 값이 항상 단조롭게 증가하거나 감소하는 상태를 유지한다는 의미에서 붙음
=> 항상 오름차순/내림차순으로 추가되는데, 그 순서가 깨지는 순간이 되면, 그 깨뜨리는 요소가 들어오기 전까지 스택에 쌓인 것들을 꺼내며 처리함

활용하면 좋을 문제 패턴

각 요소에 대해 왼쪽/오른쪽에서 처음으로 나(현재 값)보다 크거나 작은 것을 구하라.

- 오늘 이후 주가가 처음으로 떨어지는 날
- 각 건물에서 오른쪽으로 처음 보이는 더 큰 건물
- 온도가 처음으로 오르는 날까지의 기간

• 각 요소를 스택에 한번 push, 한번 pop

이미 답이 나온 요소는 다시 볼 필요가 없다 는 특성을 이용한 것
(이미 가격이 떨어진 순간이 나타났다? 그 요소는 이제 더이상 고려하지 않아도 된다는 뜻)

이번 문제 이해해보기

"가격이 떨어지지 않은 기간은 몇 초?"
= "가격이 처음으로 떨어진 초까지의 거리를 구하라!"

stack을 이용해 (아직) 가격이 떨어지지 않은 것의 인덱스만 저장하고,
새로운 가격과 비교함 (stack에 늦게 들어온 요소부터)
처음으로 자신보다 낮은 가격이 나오는 시점은 가격의 index별로 몇 초 후인지 별도로 저장

내 풀이

너무 삽질을 많이 해서 뭘 적어야 할지.. 처음엔 스택 활용할 생각도 못하고 큐 적용(?)해서 테스트케이스만 겨우 통과 > 힌트 받고 스택 사용해서 테스트 케이스만 겨우 통과(^^..) > 전혀 이해하지 못함

function solution(prices) {
    const answer = [];
    
    while (prices.length > 0) {
        const price = prices.shift();
        const lessIdx = prices.findIndex(p => p < price);
        
        if (lessIdx === -1) {
            answer.push(prices.length);
        } else {
            answer.push(lessIdx + 1);
        }
    }
    
    return answer;
}

function solution(prices) {
    const answer = new Array(prices.length).fill(0);
    const stack = [0];
    let duration = 0;
    
    for (let i = 1; i < prices.length; i++) {
        let j = stack.length - 1;
        while (prices[stack[j]] > prices[i]) {
            duration = i - stack[j];
            const index = stack.pop();
            answer[index] = duration;
        }
        
        stack.push(i);
    }
    
    for (let index of stack) {
        const d = prices.length - 1 - index;
        answer[index] = d;
    }
    
    return answer;
}

개선된 풀이

function solution(prices) {
    const answer = new Array(prices.length).fill(0);
    const stack = [];
    
    for (let i = 0; i < prices.length; i++) {
        while (stack.length > 0 && prices[stack[stack.length - 1]] > prices[i]) {
            const index = stack.pop();
            answer[index] = i - index; // 거리 저장
        }
        stack.push(i);
    }
    
    while (stack.length > 0) {
        // 끝까지 가격 떨어지지 않은 요소 거리 계산
        const index = stack.pop();
        answer[index] = prices.length - 1 - index;
    }
    
    return answer;
}

핵심 차이

• 스택 개념을 사용해 어떻게 활용하는가 그 관점

막혔던 포인트

• '가격이 떨어지지 않은 기간'의 정의가 도대체 무엇이란 말인가? 이 말의 의미를 이해하는 데 한참 걸림 (예를 들어 테스트 케이스인 [1, 2, 3, 2, 3]에서 마지막에 1을 추가한 [1, 2, 3, 2, 3, 1]이라면 prices[2] -> prices[3]으로 떨어지고 맨 뒤에 1이 나오니까 또 떨어졌다고 봐야 하는가? 하는 질문을 할 정도로.. 배열 자체만 보면 떨어진 게 맞으니까)
• 그리고 또 하나의 해프닝 발생 - 처음 answer Array를 초기화할 때 값이 없다는 의미로 -1로 채워서 테스트해봤는데 효율성 테스트 1개에서 시간 초과로 실패하는 것임. 0으로 초기화하나 -1로 초기화하나 사실 그 값을 활용하는 부분은 없어서 이게 왜 문제가 되는지 의문이었음.
  마지막 return문에서 answer에 map을 돌려서 값이 -1일 경우 0을 리턴하고 아니면 값 자체를 리턴하도록 했더니 해당 케이스(효율성 4번)에서 6ms로 빠르게 통과, 다른 케이스(효율성 2번)에서 또 타임아웃 실패함. 이 부분은 빡빡한 케이스에 map 한번 더 돌려서 실패한 것으로 보아야 할지..
  어쨌든 -1로 초기화하면 실패, 0으로 초기화하면 통과하는 이상한 지점이 있다... (캐시 비우고 다시 제출해봐도 동일한 결과)
  => 원인은 정확히 파악 불가 (효율성 케이스는 로그도 찍지 못하니까)
  다만 duration은 최솟값이 0이므로 의미상으로도 fill(0)이 맞는 초기값.
  값이 없다는 의미로 -1이 의미상 더 적절하다고도 생각했는데, fill(-1)처럼 "없음"을 표현하려면 이 문제에선 결국 후처리가 필요하고 (-1이 왜남는것임),
  그 후처리(map 순회)가 오히려 복잡도를 높이므로 fill(0)을 쓰자.

풀면서 찾은 개념

• 처음에 아예 감 못잡았을 땐 reduce도 찾고 Map 자료 구조도 찾고 이것저것 찾아봤다 .. .

다음에 비슷한 문제 만나면

• 비슷한 문제란 무엇인가 - 값이 "처음으로" "떨어진/올라간/작은/큰" 지점까지의 "거리"를 구하는 문제. 여기서의 "거리"는 지금의 '초'처럼 다소 추상적인 거리일 수도 있음.
• 일단 비슷한 문제인지 감을 잡아야 적용할 수 있을 것 같고 (그것부터가 지금의 나에겐 장벽임)
  신호 키워드: "처음으로", "다음", "거리/기간" 이 세 단어가 같이 보이면 단조 스택을 일단 의심해보기
• 감 잡고 나면 Array 를 주어진 배열 길이만큼 초기화해두고 거기에 답을 저장(그래야 정확한 순서가 보장된 답을 구할 수 있으니)한다 생각하고,
• stack에 아직 조건을 만족하지 않은 녀석들의 index를 0부터 집어넣고,
• 조건을 만족한다면 stack에서 pop하고, Array의 해당 index 값을 문제에 맞게 계산하여 저장, 조건을 만족하지 않을 때까지 반복해야 한다.
• 해당 반복문이 끝나면 이제 이번 인덱스도 stack에 넣어 다음 값이 비교군으로 사용할 수 있도록 한다.
• 이 반복문도 끝나면, 아직 stack에 남아있는 값들은 조건을 만족하지 않은 채 끝까지 버틴 값들이므로, 문제에 맞게 별도로 거리를 계산해주는데, 이때도 stack에서 하나씩 pop하면서 처리해주면 명확하다.