Dec 18, 2024

1475. Final Prices With a Special Discount in a Shop

내 코드

0ms, 14.08MB

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        // n^2
        int n = static_cast<int>(prices.size());
        vector<int> answer;
        for(int i{};i<n;++i){
            int index = i;
            for(int j{i + 1};j<n;++j) {
                if(prices[j] <= prices[i]) {
                    index = j;
                    break;
                }
            }
            if(index == i) answer.push_back(prices[i]);
            else answer.push_back(prices[i] - prices[index]);
        }
        return answer;
    }
};

Solution

Approach 1: Brute-Force

0ms, 14.11MB
Complexity
- Let $n$ be the length of the input array prices.
- Time Complexity: $O(n^2)$
- Space Complexity: $O(n)$

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        int n = prices.size();
        // Create a copy of original prices array to store discounted prices
        vector<int> result = prices;

        for (int i = 0; i < n; i++) {
            // Look for first smaller or equal price that comes after current
            // item
            for (int j = i + 1; j < n; j++) {
                if (prices[j] <= prices[i]) {
                    // Apply discount by subtracting prices[j] from current
                    // price
                    result[i] = prices[i] - prices[j];
                    break;
                }
            }
        }

        return result;
    }
};

Approach 2: Monotonic Stack

0ms, 14.32MB
Complexity
- Let $n$ be the length of the input array prices.
- Time Complexity: $O(n)$
- Space Complexity: $O(n)$

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        // Create a copy of prices array to store discounted prices
        vector<int> result = prices;

        stack<int> stack;

        for (int i = 0; i < prices.size(); i++) {
            // Process items that can be discounted by current price
            while (!stack.empty() && prices[stack.top()] >= prices[i]) {
                // Apply discount to previous item using current price
                result[stack.top()] -= prices[i];
                stack.pop();
            }
            // Add current index to stack
            stack.push(i);
        }

        return result;
    }
};

GPT

아래 코드는 단조(stack)를 활용하여 각 가격에 대해 “오른쪽에 있는 (나중에 오는) 가격 중 현재 가격 이하인 첫 가격”을 찾아 그 값만큼 할인해 주는 전형적인 문제를 해결하는 방식입니다. 이를 단계별로 살펴보겠습니다.

문제 배경

prices 배열이 주어집니다.
각 prices[i]에 대해, i 이후(i+1, i+2, …)에 있는 가격들 중 처음으로 prices[i] 이상이 아닌(즉, <= prices[i]) 가격이 있다면, 그 가격만큼 할인해주려 합니다.
해당 가격이 없다면 할인은 적용되지 않습니다.

예)

만약 prices = [8,4,6,2,3]라면,
1. prices[0] = 8: 이후 가격 중 처음으로 8 이하인 값은 4. 따라서 최종 가격은 8 - 4 = 4.
2. prices[1] = 4: 이후 가격 중 처음으로 4 이하인 값은 2. 따라서 최종 가격은 4 - 2 = 2.
3. prices[2] = 6: 이후 가격 중 처음으로 6 이하인 값은 2. 따라서 최종 가격은 6 - 2 = 4.
4. prices[3] = 2: 이후 가격 중 2 이하인 값은 없으므로 할인 없음 → 2.
5. prices[4] = 3: 오른쪽에 원소가 없으므로 할인 없음 → 3.
- 결과적으로 [4, 2, 4, 2, 3]이 됩니다.

코드 설명

vector<int> finalPrices(vector<int>& prices) {
    // 결과(할인 적용된 가격)를 담을 벡터. 처음엔 원본 그대로 복사
    vector<int> result = prices;

    // 인덱스를 저장할 스택
    stack<int> stack;

    for (int i = 0; i < prices.size(); i++) {
        // 스택이 비어있지 않고,
        // 스택의 top에 있는 인덱스 j에 대해 prices[j] >= prices[i] 라면
        // → j번째 가격을 i번째 가격으로 할인 가능
        while (!stack.empty() && prices[stack.top()] >= prices[i]) {
            // j번째 상품의 결과 가격에서 prices[i] 만큼 할인
            result[stack.top()] -= prices[i];
            stack.pop();
        }

        // 현재 인덱스 i를 스택에 푸시
        stack.push(i);
    }

    return result;
}

핵심 아이디어: 단조 증가 스택 (Monotonic Stack)

스택 안에는 아직 할인 처리가 되지 않은 인덱스들을 저장합니다.
prices[j] >= prices[i]를 만족하면, j번째 가격은 i번째 가격으로부터 할인이 가능하므로 처리해주고 스택에서 제외(pop)합니다.
이렇게 처리하고 나면, j번째 가격에 대해 해당 조건을 만족하는 첫 번째(오른쪽에서 제일 가까운) 할인 가격을 찾게 됩니다.

과정 요약

반복문: i를 0부터 prices.size() - 1까지 순회
while 루프: 스택이 비지 않았고,
- 스택 top의 인덱스 j에 대해 prices[j] >= prices[i]이면:
  - result[j]에 prices[i]만큼 할인 적용
  - j를 스택에서 꺼냄
- 스택 top의 가격이 prices[i]보다 작으면, 할인 조건 불충족이므로 멈춤
현재 인덱스 i 스택에 삽입
- 아직 할인 처리가 되지 않은 i번째 상품을 스택에 넣어, 나중에 i+1, i+2…번째에서 할인 가격을 찾을 수 있도록 준비
반복문 종료 후: 스택에 남아 있는 인덱스는 오른쪽에 자신보다 작거나 같은 가격이 없으므로 할인 없이 그대로 남음

예시 동작

prices = [8,4,6,2,3]
- i=0: 스택 비어 있음 → push(0) → stack = [0] (값으로 치면 [8])
- i=1:
  - top=0, prices[0]=8 >= prices[1]=4 → result[0] = 8 - 4 = 4, pop(0)
  - 스택이 비었으므로 while 종료
  - push(1) → stack = [1] (값으로 [4])
- i=2:
  - top=1, prices[1]=4 >= prices[2]=6 ? No. 4 < 6 → while 종료
  - push(2) → stack = [1,2] (값으로 [4,6])
- i=3:
  - top=2, prices[2]=6 >= prices[3]=2 → result[2] = 6 - 2 = 4, pop(2)
  - top=1, prices[1]=4 >= prices[3]=2 → result[1] = 4 - 2 = 2, pop(1)
  - 스택 비었으므로 while 종료
  - push(3) → stack = [3] (값으로 [2])
- i=4:
  - top=3, prices[3]=2 >= prices[4]=3? No. 2 < 3 → while 종료
  - push(4) → stack = [3,4] (값으로 [2,3])
- 반복 끝
- 스택에 남은 [3,4]는 할인 적용 기회 없음 → result[3]=2, result[4]=3 그대로 유지
- 최종 result = [4,2,4,2,3]

결론

Monotonic Stack 기법으로, 각 원소(가격)에 대해 오른쪽에서 처음으로 자신보다 작거나 같은 값을 빠르게 찾아 할인 가격을 계산하는 로직입니다.
시간 복잡도는 $O(n)$ 수준으로, 단순 이중 반복(naive) 접근 시 $O(n^2)$ 가 될 문제를 스택을 활용해 효율적으로 해결합니다.

Monotonic Stack

Monotonic Stack은 스택을 이용하여 단조 증가(Increasing) 또는 단조 감소(Decreasing)의 특성을 유지하면서, 데이터를 처리하는 기법을 말합니다. 쉽게 말해서, 스택에 들어 있는 원소가 어떤 일정한 순서를(오름차순 또는 내림차순) 유지하도록 쌓아두는 방식입니다.

Monotonic Stack의 종류

단조 증가 스택 (Monotonically Increasing Stack)
- 스택에 들어가는 값들이 오름차순(증가) 을 유지하도록 관리합니다.
- 즉, 스택의 top에 있는 값이 새로 들어오는 값보다 작거나 같을 경우에는 더 이상 오름차순이 유지되지 않으므로, top에 있는 값들을 제거(pop)합니다.
단조 감소 스택 (Monotonically Decreasing Stack)
- 스택에 들어가는 값들이 내림차순(감소) 을 유지하도록 관리합니다.
- 즉, 스택의 top에 있는 값이 새로 들어오는 값보다 크거나 같을 경우에는 더 이상 내림차순이 유지되지 않으므로, top에 있는 값들을 제거(pop)합니다.

이렇게 값이 들어오면서 stack의 top과 비교하여, 해당 조건(오름차순/내림차순)이 깨지면 pop을 하는 과정을 반복하면, 최종적으로 스택에는 단조 성질을 만족하는 인덱스(또는 값)만 남게 됩니다.

Monotonic Stack이 왜 유용할까?

주요 용도
- 다음에 오는(또는 이전에 나왔던) 큰/작은 원소 탐색
  - “다음 큰 원소(Next Greater Element)”를 찾거나, “다음 작은 원소(Next Smaller Element)”를 찾는 문제에 활용됩니다.
- 주가 예측, 기온 예측 등: “오른쪽에서 처음으로 자신보다 큰 값” 혹은 “오른쪽에서 처음으로 자신보다 작은 값”을 빠르게 찾을 때 사용됩니다.
- 배열에서 특정 조건을 만족하는 구간 찾기: 예를 들어, “연속된 구간에서 최솟값/최댓값” 등을 효율적으로 구할 때도 Monotonic Stack 기법이 확장되어 쓰입니다.
시간 복잡도
- Monotonic Stack을 사용하면 보통 $O(n)$ 시간에 문제를 해결할 수 있습니다.
- 배열을 단순 이중 반복문으로 처리하면 $O(n^2)$ 가 될 수도 있는 문제에서, Monotonic Stack으로 한 번의 pass(또는 두 번의 pass)로 처리 가능하게 됩니다.
- 스택에 각 원소는 최대 한 번 push되고, 조건이 맞지 않을 때 최대 한 번 pop되기 때문입니다.

동작 원리 예시: “오른쪽에서 처음으로 자신보다 작은 원소 찾기”

예를 들어, prices = [8, 4, 6, 2, 3]이고, “오른쪽에서 처음으로 <= 현재값인 원소”를 찾아서 작업해야 한다고 합시다(대표적으로 할인 가격 문제 등).

스택에 인덱스를 저장하되, 스택에는 “아직 자신보다 작은 혹은 같은 값을 만나지 못한 인덱스”들을 유지합니다.
새로운 원소 prices[i]를 확인할 때마다,
- 스택이 비어 있지 않고, 스택 top에 있는 인덱스 j가 가리키는 값 prices[j] >= prices[i]이면,
  - 이는 j번째 원소가 오른쪽에서 처음으로 만난 자신보다 작거나 같은 값이 i임을 의미합니다.
  - j를 pop하고, j번째 원소에 대해서 “오른쪽에서 처음 발견한 작은(또는 같은) 값”이 prices[i]라는 것을 기록합니다.
- 이 과정을 더 이상 만족하지 않을 때까지 반복(pop)한 후, i를 push합니다.
스택에 남아있는 인덱스는 오른쪽에서 자신보다 작거나 같은 값이 없는 상태이므로, 필요한 경우 해당 인덱스에 대해 다른 처리를 합니다.

예시 동작

prices = [8, 4, 6, 2, 3]
- i=0 → 스택 empty → push(0) → stack=[0] (값: [8])
- i=1 → top=0, prices[0]=8 >= prices[1]=4 → pop(0)
  - “0번 값(8)은 오른쪽에서 처음 만난 자신보다 작거나 같은 값이 4”
  - stack empty → push(1) → stack=[1] (값: [4])
- i=2 → top=1, prices[1]=4 >= 6? No → push(2) → stack=[1,2] (값: [4,6])
- i=3 → top=2, prices[2]=6 >= 2 → pop(2)
  - “2번 값(6)은 오른쪽에서 처음 만난 작거나 같은 값이 2”
  - top=1, prices[1]=4 >= 2 → pop(1)
    - “1번 값(4)은 오른쪽에서 처음 만난 작거나 같은 값이 2”
  - stack empty → push(3) → stack=[3] (값: [2])
- i=4 → top=3, prices[3]=2 >= 3? No → push(4) → stack=[3,4] (값: [2,3])
- 완료 → stack=[3,4]는 오른쪽에 자신보다 작거나 같은 값이 없음을 뜻함

이 과정을 통해 각 원소가 어디에서 처음으로 자신보다 작은(또는 같은) 원소를 만나게 되는지를 O(n) 시간 안에 구할 수 있습니다.

Monotonic Stack의 장점 정리

한 번의 스캔으로 해결 (또는 2번, 문제 따라 다름)
중간 계산(누가 누구를 할인해주는지, 누가 누구보다 큰지/작은지 등)을 빠르게 업데이트
효율성: 원소가 스택에 들어갔다가 나오는 과정이 최대 1번씩만 일어나므로, 전체 연산 횟수는 O(n)에 수렴

결론

Monotonic Stack은 배열에서 인접한(오른쪽 혹은 왼쪽) 큰/작은 원소를 효율적으로 찾는 핵심적인 알고리즘 패턴입니다.
가격 할인, 주가 분석, 온도 분석(“다음에 나오는 더 높은/낮은 온도는 언제인가?”) 등 다양한 상황에서 두루 사용됩니다.
스택의 top과 비교해 조건이 깨지는 순간(오름차순/내림차순이 더 이상 유지되지 않는 순간) pop을 수행하며, 그 때의 새로운 원소가 바로 ‘다음 큰(작은) 원소’ 가 됩니다.
이러한 아이디어로 복잡도를 $O(n)$ 안에서 해결할 수 있다는 점이 가장 큰 장점입니다.