스택과 큐를 활용한 자료 구조 문제 해결 전략

스택과 큐는 컴퓨터 과학에서 가장 기본적이고 널리 사용되는 선형 자료 구조입니다. 이 두 가지 구조는 데이터를 저장하고 접근하는 방식에 있어 명확한 차이를 가지며, 다양한 알고리즘 문제 해결에 필수적인 도구로 활용됩니다. 스택은 '후입선출(LIFO: Last In, First Out)' 원칙을 따르며, 큐는 '선입선출(FIFO: First In, First Out)' 원칙을 따릅니다. 특히 스택은 괄호 매칭이나 역순 처리와 같은 문제에, 큐는 너비 우선 탐색(BFS)이나 순차적 처리에 강점을 보입니다.

스택과 큐를 사용할 때 주의할 점은 요소를 제거(pop)하기 전에 반드시 비어있는지 확인해야 한다는 것입니다. 잘못된 접근은 프로그램 오류로 이어질 수 있습니다.

자료 구조 주요 기능 대표적인 문제 유형
일반 스택 짝 맞추기, 요소 제거, 역순 처리 괄호 유효성 검사, 인접 중복 문자 제거, 역폴란드 표기법 계산
일반 큐 순차적 처리, BFS, 대기열 관리 너비 우선 탐색(BFS), 레벨 순서 순회
단조 스택 '첫 번째로 더 크거나 작은' 요소 찾기 일일 온도, 빗물 트랩, 최대 직사각형
단조 큐 슬라이딩 윈도우 내 최댓값/최솟값 빠른 조회 슬라이딩 윈도우 최댓값

이 글에서는 스택과 큐의 기본적인 활용법과 구현 패턴, 그리고 이를 이용한 다양한 문제 해결 기법에 대해 자세히 살펴보겠습니다.

1. 스택으로 큐 구현하기

스택 두 개를 사용하여 큐의 동작을 모방할 수 있습니다. 주로 데이터를 입력받는 스택(inputStack)과 데이터를 출력하는 스택(outputStack)을 활용합니다. 이 방식을 사용하면 큐의 FIFO 원칙을 스택의 LIFO 원칙 위에 구현할 수 있습니다.

  • 데이터 삽입 (enqueue): 새 요소는 inputStack에 평범하게 추가됩니다.
  • 데이터 제거 및 반환 (dequeue): outputStack이 비어있을 때만, inputStack의 모든 요소를 outputStack으로 옮깁니다. 그 후, outputStack에서 최상단 요소를 제거하고 반환합니다. 이는 inputStack의 가장 오래된 요소가 outputStack의 최상단으로 오게 하여 큐의 순서를 맞추기 위함입니다.
  • 큐의 맨 앞 요소 확인 (peek): 제거 로직과 유사하게, outputStack이 비어있으면 inputStack의 모든 요소를 outputStack으로 옮긴 후, outputStack의 최상단 요소를 반환합니다. 이 경우 요소는 제거하지 않습니다.
class MyQueue {
private:
    std::stack<int> inputStack;  // 입력용 스택
    std::stack<int> outputStack; // 출력용 스택

    // inputStack의 모든 요소를 outputStack으로 이동
    void transferElements() {
        if (outputStack.empty()) {
            while (!inputStack.empty()) {
                outputStack.push(inputStack.top());
                inputStack.pop();
            }
        }
    }

public:
    MyQueue() {}

    void push(int x) {
        inputStack.push(x);
    }

    int pop() {
        transferElements();
        int frontElement = outputStack.top();
        outputStack.pop();
        return frontElement;
    }

    int peek() {
        transferElements();
        return outputStack.top();
    }

    bool empty() {
        return inputStack.empty() && outputStack.empty();
    }
};

2. 큐로 스택 구현하기

하나의 큐를 사용하여 스택의 LIFO 동작을 시뮬레이션할 수 있습니다. 이 방법은 여러 개의 큐를 사용하는 것보다 구현이 간단하고 이해하기 쉽습니다.

  • 데이터 삽입 (push): 새 요소는 큐의 맨 뒤에 정상적으로 추가됩니다.
  • 데이터 제거 및 반환 (pop): 스택의 LIFO 동작을 위해, 큐의 맨 뒤 요소(가장 최근에 추가된 요소)를 제외한 모든 요소를 큐에서 제거한 후 다시 큐의 맨 뒤에 추가합니다. 마지막으로 남아있는 원래의 맨 뒤 요소를 제거하고 반환합니다.
  • 스택의 최상단 요소 확인 (top): 제거 로직과 유사하게 큐의 맨 뒤 요소를 제외한 모든 요소를 큐에서 제거 후 다시 뒤에 추가합니다. 그리고 맨 뒤 요소를 확인한 후, 이 요소 또한 다시 큐의 맨 뒤에 추가하여 원래의 순서를 유지합니다. 더 간단하게는 std::queue의 back() 메소드를 활용할 수도 있습니다.

3. 유효한 괄호

주어진 문자열 s가 '(', ')', '{', '}', '[', ']' 문자들로만 이루어져 있을 때, 이 괄호 문자열이 유효한지 판단하는 문제입니다. 유효한 문자열은 다음과 같은 조건을 만족해야 합니다.

  • 같은 종류의 여는 괄호는 같은 종류의 닫는 괄호로 닫혀야 합니다.
  • 여는 괄호는 올바른 순서로 닫혀야 합니다.
  • 모든 닫는 괄호에는 상응하는 여는 괄호가 있어야 합니다.

이 문제는 스택을 사용하여 해결하기에 매우 적합합니다. 주요 불일치 시나리오는 세 가지입니다.

  • 여는 괄호가 더 많은 경우: 문자열을 모두 탐색한 후에도 스택이 비어있지 않은 경우입니다.
  • 닫는 괄호가 더 많은 경우: 닫는 괄호를 만나 스택에서 짝을 찾으려 할 때 스택이 이미 비어있는 경우입니다.
  • 괄호 종류가 일치하지 않는 경우: 여는 괄호와 닫는 괄호의 종류가 서로 다른 경우입니다.

해결 전략: 문자열을 순회하면서 여는 괄호((, {, [)를 만나면 해당 괄호에 상응하는 닫는 괄호를 스택에 푸시합니다. 닫는 괄호(), }, ])를 만나면 스택이 비어있는지 확인하고, 비어있지 않으면 스택의 최상단 요소를 팝하여 현재 닫는 괄호와 비교합니다. 두 괄호가 일치하면 계속 진행하고, 일치하지 않거나 스택이 비어있으면 즉시 false를 반환합니다. 문자열 탐색이 완료된 후 스택이 비어있으면 true를, 비어있지 않으면 false를 반환합니다.

4. 문자열에서 모든 인접한 중복 항목 제거

소문자 알파벳으로 이루어진 문자열 S가 주어졌을 때, 인접하고 동일한 두 문자를 찾아 제거하는 작업을 반복하여 최종 문자열을 반환하는 문제입니다. 이 과정은 더 이상 제거할 항목이 없을 때까지 수행됩니다. 결과는 항상 유일함이 보장됩니다.

해결 전략: 이 문제는 스택의 LIFO 특성을 활용하여 쉽게 해결할 수 있습니다. 문자열을 순회하면서 각 문자를 처리합니다.

  • 스택이 비어있거나 현재 문자가 스택의 최상단 문자와 다르면 현재 문자를 스택에 푸시합니다.
  • 스택이 비어있지 않고 현재 문자가 스택의 최상단 문자와 같으면, 중복된 문자를 제거하기 위해 스택의 최상단 요소를 팝합니다.

문자열 탐색이 완료되면 스택에 남아있는 요소들을 역순으로 합쳐 최종 결과 문자열을 만듭니다. (스택은 LIFO이므로, 푸시된 순서의 역순으로 팝되기 때문입니다.)

std::string removeDuplicates(std::string S) {
    std::stack<char> charStack;
    for (char currentChar : S) {
        if (charStack.empty() || currentChar != charStack.top()) {
            charStack.push(currentChar);
        } else {
            charStack.pop(); // currentChar가 스택 최상단과 같은 경우
        }
    }

    std::string finalResult = "";
    while (!charStack.empty()) {
        finalResult += charStack.top();
        charStack.pop();
    }
    std::reverse(finalResult.begin(), finalResult.end()); // 스택에서 꺼낸 순서는 역순이므로 뒤집기
    return finalResult;
}

또는 실제 스택 자료구조 대신 일반 문자열을 스택처럼 활용하여 더 간결하게 구현할 수도 있습니다. 새 문자열(resultStr)을 스택처럼 사용하여, push_back과 pop_back 연산을 수행합니다.

std::string removeDuplicatesOptimized(std::string S) {
    std::string resultStr;
    for (char currentChar : S) {
        if (resultStr.empty() || resultStr.back() != currentChar) {
            resultStr.push_back(currentChar);
        } else {
            resultStr.pop_back(); // resultStr의 마지막 문자와 currentChar가 같은 경우
        }
    }
    return resultStr;
}

5. 역폴란드 표현식 평가

역폴란드 표기법(Reverse Polish Notation, RPN)으로 주어진 산술 표현식을 계산하는 문제입니다. RPN은 연산자가 피연산자 뒤에 오는 표기법으로, 연산자 우선순위를 고려할 필요가 없어 컴퓨터 연산에 적합합니다.

해결 전략: 숫자와 연산자를 처리하기 위해 스택을 사용합니다.

  • 표현식을 순회하면서 숫자를 만나면 스택에 푸시합니다.
  • 연산자(+, -, *, /)를 만나면 스택에서 두 개의 피연산자를 팝(operand2, operand1 순서로)하여 해당 연산을 수행합니다. 연산 결과를 다시 스택에 푸시합니다.
  • 표현식 탐색이 완료되면 스택에 남아있는 마지막 요소가 최종 계산 결과입니다.

6. 슬라이딩 윈도우 최댓값 (단조 큐)

정수 배열 nums와 슬라이딩 윈도우의 크기 k가 주어졌을 때, 윈도우가 배열의 가장 왼쪽에서 가장 오른쪽으로 이동하면서 각 윈도우 내의 최댓값을 반환하는 문제입니다.

해결 전략: 이 문제는 단조 감소 큐(Monotonically Decreasing Deque)를 사용하여 효율적으로 해결할 수 있습니다. 큐는 항상 내부에 있는 요소들을 내림차순으로 유지합니다. 큐의 맨 앞(front)에는 항상 현재 윈도우의 최댓값이 위치하게 됩니다.

  • 요소 삽입 (push_element): 큐에 새 요소를 삽입할 때, 큐의 맨 뒤에서부터 현재 요소보다 작은 모든 요소를 제거합니다. 그 후 현재 요소를 큐의 맨 뒤에 추가합니다. 이로써 큐는 항상 내림차순을 유지하고, 맨 앞에는 최댓값이 오도록 합니다.
  • 요소 제거 (pop_element): 윈도우가 이동하여 배열의 가장 왼쪽에서 벗어나는 요소(valueToRemove)가 있을 때, 이 요소가 현재 큐의 맨 앞(최댓값)과 같다면 큐에서 제거합니다. valueToRemove가 큐의 맨 앞과 다르면, 이미 push_element 과정에서 제거되었음을 의미하므로 아무 작업도 하지 않습니다.
  • 최댓값 조회 (get_max): 큐의 맨 앞 요소를 반환하면 됩니다.

주 함수 로직:

  1. 초기 k개 요소를 큐에 삽입하고, 첫 번째 윈도우의 최댓값을 결과 배열에 기록합니다.
  2. 인덱스 k부터 배열의 끝까지 순회하면서 윈도우를 한 칸씩 이동합니다. 각 단계에서 이전 윈도우의 가장 왼쪽 요소를 제거하고 새 윈도우의 가장 오른쪽 요소를 삽입합니다. 그리고 현재 윈도우의 최댓값을 결과 배열에 기록합니다.
  3. 최종적으로 결과 배열을 반환합니다.
class MonotonicQueue {
public:
    std::deque<int> dataDeque; // 단조 감소 큐

    // 큐의 맨 앞에서 요소 제거
    void pop_element(int valueToRemove) {
        if (!dataDeque.empty() && valueToRemove == dataDeque.front()) {
            dataDeque.pop_front();
        }
    }

    // 큐의 맨 뒤에 요소 삽입 (단조성 유지)
    void push_element(int newValue) {
        while (!dataDeque.empty() && newValue > dataDeque.back()) {
            dataDeque.pop_back();
        }
        dataDeque.push_back(newValue);
    }

    // 현재 큐의 최댓값 (맨 앞 요소) 반환
    int get_max() {
        return dataDeque.front();
    }
};

std::vector<int> slidingWindowMaximum(const std::vector<int>& nums, int k) {
    MonotonicQueue windowQ;
    std::vector<int> maxValues;

    // 초기 k개 요소로 윈도우 채우기
    for (int i = 0; i < k; i++) {
        windowQ.push_element(nums[i]);
    }
    maxValues.push_back(windowQ.get_max()); // 첫 번째 윈도우의 최댓값 기록

    // 윈도우 이동
    for (int i = k; i < nums.size(); i++) {
        windowQ.pop_element(nums[i - k]);   // 윈도우를 벗어나는 요소 제거
        windowQ.push_element(nums[i]);      // 윈도우에 새로 들어오는 요소 추가
        maxValues.push_back(windowQ.get_max()); // 현재 윈도우의 최댓값 기록
    }

    return maxValues;
}

7. 상위 K개 빈도 요소

정수 배열 nums와 정수 k가 주어졌을 때, 배열에서 빈도수가 가장 높은 상위 k개의 요소를 반환하는 문제입니다. 반환 순서는 상관없습니다.

해결 전략 (간단한 접근):

  1. 먼저 해시 맵(예: std::map 또는 std::unordered_map)을 사용하여 각 숫자의 빈도수를 계산합니다.
  2. 맵에 저장된 (숫자, 빈도수) 쌍을 벡터로 옮긴 후, 빈도수를 기준으로 내림차순으로 정렬합니다.
  3. 정렬된 벡터에서 상위 k개의 요소를 추출하여 반환합니다.

더 효율적인 방법으로는 최소 힙(Min-Heap)을 사용하여 상위 K개 요소를 O(N log K) 시간에 찾는 방법이 있지만, 이는 힙 자료구조에 대한 이해가 필요합니다.

단조 스택 활용

단조 스택은 스택 내의 요소들이 특정 순서(오름차순 또는 내림차순)를 유지하도록 관리되는 스택입니다. 이 자료구조는 주로 배열에서 "현재 요소의 왼쪽/오른쪽에서 처음으로 더 크거나 작은 요소"를 찾는 문제에 매우 효과적입니다. 배열이 원형으로 연결되어 있거나 순환 구조를 가질 때는 나머지 연산(%)을 활용하여 인덱스를 처리할 수 있습니다.

1. 일일 온도

매일의 온도를 나타내는 정수 배열 temperatures가 주어졌을 때, answer[i]는 i번째 날로부터 며칠 뒤에 다음으로 더 높은 온도가 나타나는지를 의미합니다. 이후에 더 높은 온도가 없다면 0을 기록합니다.

해결 전략: 이 문제는 단조 스택을 사용하여 "오른쪽에서 처음으로 더 높은 온도"를 찾는 전형적인 문제입니다. 스택에는 온도의 인덱스를 저장하며, 스택은 단조 감소(탑부터 바닥으로 갈수록 증가)를 유지하도록 관리합니다.

  • 현재 온도를 순회하며 처리합니다.
  • 현재 온도가 스택이 비어있거나 스택 최상단 인덱스의 온도보다 작거나 같으면, 현재 인덱스를 스택에 푸시합니다. 이는 단조 감소를 유지하거나(작은 경우) 짝을 찾지 못했음(같은 경우)을 의미합니다.
  • 현재 온도가 스택 최상단 인덱스의 온도보다 크면, 스택에서 현재 온도보다 작은 인덱스를 모두 팝합니다. 팝되는 각 인덱스 j에 대해 answer[j]는 현재 인덱스 - j가 됩니다. 이 과정을 반복한 후 현재 인덱스를 스택에 푸시합니다.
  • 탐색이 끝난 후 스택에 남아있는 인덱스들에 대해서는 answer 값을 0으로 설정합니다.
std::vector<int> dailyTemperatures(const std::vector<int>& temps) {
    int n = temps.size();
    std::vector<int> answer(n, 0);
    std::stack<int> indexStack; // 인덱스를 저장하는 스택

    for (int i = 0; i < n; ++i) {
        // 현재 온도가 스택 최상단의 온도보다 높으면
        while (!indexStack.empty() && temps[i] > temps[indexStack.top()]) {
            int prevIndex = indexStack.top();
            indexStack.pop();
            answer[prevIndex] = i - prevIndex; // 더 높은 온도를 찾았으므로 거리 계산
        }
        indexStack.push(i); // 현재 인덱스를 스택에 푸시
    }
    return answer;
}

2. 다음 큰 요소 I

두 배열 nums1과 nums2가 주어지며, nums1은 nums2의 부분집합이고 중복 요소는 없습니다. nums1의 각 숫자 x에 대해, nums2에서 x의 위치 오른쪽에 있는 숫자 중 처음으로 x보다 큰 요소를 찾아 반환합니다. 없으면 -1을 반환합니다.

해결 전략: 이 문제는 nums2에 대해 "다음 큰 요소"를 먼저 계산하고, 그 결과를 맵에 저장하여 nums1의 요소들을 빠르게 조회하는 방식으로 해결합니다.

  1. nums1의 각 요소와 그 인덱스를 매핑하는 해시 맵(val -> index)을 생성하여 nums1의 요소를 O(1) 시간에 찾을 수 있도록 준비합니다.
  2. nums2 배열을 순회하면서 단조 스택을 이용하여 각 요소의 "다음 큰 요소"를 찾습니다. 스택에는 nums2의 인덱스를 저장합니다.
    • 현재 nums2 요소 nums2[i]가 스택 최상단 인덱스 st.top()에 해당하는 nums2[st.top()]보다 작거나 같으면, i를 스택에 푸시합니다.
    • nums2[i]가 nums2[st.top()]보다 크면, 스택에서 nums2[i]보다 작은 요소들을 모두 팝합니다. 팝된 각 인덱스 prevIdx에 대해 nums2[i]가 nums2[prevIdx]의 "다음 큰 요소"가 됩니다. 만약 nums2[prevIdx]가 nums1에 존재한다면, 결과 배열에 nums2[i]를 기록합니다. 이 과정이 끝나면 i를 스택에 푸시합니다.
  3. 초기 결과 배열은 nums1의 크기만큼 -1로 채워놓습니다.
std::vector<int> nextGreaterElement(const std::vector<int>& nums1, const std::vector<int>& nums2) {
    std::unordered_map<int, int> num1IndexMap; // nums1의 값 -> 인덱스 매핑
    for (int i = 0; i < nums1.size(); ++i) {
        num1IndexMap[nums1[i]] = i;
    }

    std::vector<int> result(nums1.size(), -1); // 결과 배열을 -1로 초기화
    std::stack<int> monoStack; // 단조 스택 (nums2의 인덱스 저장)

    for (int i = 0; i < nums2.size(); ++i) {
        // 현재 nums2[i]가 스택 최상단 요소보다 크면, 다음 큰 요소 발견
        while (!monoStack.empty() && nums2[i] > nums2[monoStack.top()]) {
            int poppedIndex = monoStack.top();
            monoStack.pop();
            // 팝된 요소가 nums1에 있다면 결과에 기록
            if (num1IndexMap.count(nums2[poppedIndex])) {
                result[num1IndexMap[nums2[poppedIndex]]] = nums2[i];
            }
        }
        monoStack.push(i); // 현재 인덱스 스택에 푸시
    }
    return result;
}

3. 다음 큰 요소 II (순환 배열)

주어진 순환 배열 nums (nums[nums.length - 1] 다음 요소는 nums[0])의 각 요소에 대해 "다음 큰 요소"를 찾습니다. 없으면 -1을 반환합니다.

해결 전략: 순환 배열의 특성을 처리하기 위해 두 가지 주요 접근 방식이 있습니다.

해결책 1: 배열 복사 (간단하지만 메모리 사용)

가장 직관적인 방법은 nums 배열을 한 번 더 복사하여 자기 뒤에 붙여 [nums[0], ..., nums[N-1], nums[0], ..., nums[N-1]]와 같은 길이 2N의 배열을 만드는 것입니다. 이 새로운 배열에 대해 일반적인 "다음 큰 요소" 알고리즘을 적용한 후, 최종 결과 배열의 크기를 원래 N으로 조절합니다.

해결책 2: 나머지 연산 활용 (효율적)

배열을 두 번 순회하는 것처럼 인덱스를 i % N 형태로 사용하여 순환 배열을 시뮬레이션할 수 있습니다. 2N-1까지의 인덱스를 순회하며, 실제 배열의 값에 접근할 때는 nums[i % N]을 사용합니다. 스택에는 인덱스 i % N를 저장합니다.

std::vector<int> nextGreaterElementsCircular(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> result(n, -1);
    std::stack<int> indexStack; // 인덱스를 저장하는 스택

    // 배열을 두 번 순회하는 효과를 위해 0부터 2*n-1까지 반복
    for (int i = 0; i < 2 * n; ++i) {
        int currentIdx = i % n;
        // 현재 요소가 스택 최상단 인덱스에 해당하는 값보다 크면
        while (!indexStack.empty() && nums[currentIdx] > nums[indexStack.top()]) {
            result[indexStack.top()] = nums[currentIdx]; // 다음 큰 요소 기록
            indexStack.pop();
        }
        // 첫 번째 순회(i < n)일 때만 스택에 인덱스 푸시 (중복 방지 및 올바른 결과 보장)
        if (i < n) { 
            indexStack.push(currentIdx);
        }
    }
    return result;
}

이 방법은 스택에 마지막까지 남아있는 요소들은 자신보다 큰 요소를 찾지 못한 경우이며, 이는 원형 배열에서도 마찬가지입니다. 따라서 이전 결과를 덮어쓰지 않고 올바른 결과를 얻습니다.

4. 빗물 트랩

높이가 1인 기둥들의 높이 정보를 나타내는 n개의 음이 아닌 정수가 주어졌을 때, 비가 온 후 모일 수 있는 빗물의 총량을 계산하는 문제입니다.

이 문제는 세 가지 주요 해결책이 있습니다.

해결책 1: 브루트 포스 (수직 탐색)

각 기둥을 기준으로 그 왼쪽과 오른쪽에서 가장 높은 기둥을 찾아 빗물을 계산합니다. 첫 번째와 마지막 기둥에는 빗물이 고일 수 없으므로 무시합니다. 각 기둥 i에 대해 왼쪽에서 가장 높은 기둥 maxLeft[i]와 오른쪽에서 가장 높은 기둥 maxRight[i]를 찾습니다. 현재 기둥에 고일 수 있는 빗물의 양은 min(maxLeft[i], maxRight[i]) - height[i]입니다. 이 값을 모든 기둥에 대해 합산합니다.

int trapBruteForce(const std::vector<int>& barHeights) {
    int n = barHeights.size();
    if (n <= 2) return 0; // 빗물이 고일 수 없는 경우
    int totalWater = 0;

    for (int i = 1; i < n - 1; ++i) { // 첫 번째와 마지막 기둥 제외
        int maxLeftHeight = barHeights[i];
        int maxRightHeight = barHeights[i];

        // 현재 기둥의 왼쪽에서 가장 높은 기둥 찾기
        for (int l = i - 1; l >= 0; --l) {
            maxLeftHeight = std::max(maxLeftHeight, barHeights[l]);
        }
        // 현재 기둥의 오른쪽에서 가장 높은 기둥 찾기
        for (int r = i + 1; r < n; ++r) {
            maxRightHeight = std::max(maxRightHeight, barHeights[r]);
        }

        // 현재 기둥에 고이는 빗물 계산
        int currentBarWater = std::min(maxLeftHeight, maxRightHeight) - barHeights[i];
        if (currentBarWater > 0) {
            totalWater += currentBarWater;
        }
    }
    return totalWater;
}

해결책 2: 동적 계획법 (전처리)

브루트 포스 방식에서 매번 왼쪽/오른쪽 최고 높이를 다시 계산하는 비효율성을 개선합니다. 두 개의 배열 leftMax와 rightMax를 미리 계산하여 각 기둥 위치까지의 왼쪽 최고 높이와 오른쪽 최고 높이를 저장합니다.

  1. leftMax[i]: 인덱스 0부터 i까지의 최고 높이 (barHeights[i] 포함).
  2. rightMax[i]: 인덱스 i부터 n-1까지의 최고 높이 (barHeights[i] 포함).

이 배열들을 한 번씩 순회하여 채운 후, 다시 배열을 순회하며 min(leftMax[i], rightMax[i]) - barHeights[i]를 계산하여 총 빗물 양을 합산합니다.

int trapDynamicProgramming(const std::vector<int>& heightsArr) {
    int N = heightsArr.size();
    if (N <= 2) return 0;

    std::vector<int> leftMaxArray(N);
    std::vector<int> rightMaxArray(N);

    // 각 위치까지의 왼쪽 최고 높이 계산
    leftMaxArray[0] = heightsArr[0];
    for (int i = 1; i < N; ++i) {
        leftMaxArray[i] = std::max(heightsArr[i], leftMaxArray[i - 1]);
    }

    // 각 위치까지의 오른쪽 최고 높이 계산
    rightMaxArray[N - 1] = heightsArr[N - 1];
    for (int i = N - 2; i >= 0; --i) {
        rightMaxArray[i] = std::max(heightsArr[i], rightMaxArray[i + 1]);
    }

    int collectedWater = 0;
    for (int i = 0; i < N; ++i) {
        // 현재 기둥에 고이는 빗물 계산
        int currentWater = std::min(leftMaxArray[i], rightMaxArray[i]) - heightsArr[i];
        if (currentWater > 0) {
            collectedWater += currentWater;
        }
    }
    return collectedWater;
}

해결책 3: 단조 스택 (수평 탐색)

단조 스택은 빗물을 "층별로" 계산하는 수평 탐색 방식으로 문제를 해결합니다. 스택에는 기둥의 인덱스를 저장하며, 스택은 단조 감소를 유지합니다.

  • 배열을 순회하면서 현재 기둥 heights[i]를 처리합니다.
  • 현재 기둥이 스택 최상단의 기둥보다 작거나 같으면, 현재 인덱스 i를 스택에 푸시합니다.
  • 현재 기둥이 스택 최상단의 기둥보다 크면, 스택에서 heights[i]보다 작은 기둥(poppedIdx)을 팝합니다. 팝된 기둥이 "골짜기"의 바닥 역할을 합니다.
    • poppedIdx를 팝한 후 스택이 비어있지 않다면, 새 스택 최상단(leftBoundaryIdx)이 골짜기의 왼쪽 경계가 되고, 현재 기둥 i가 오른쪽 경계가 됩니다.
    • 이때 고이는 빗물의 높이 h는 min(heights[leftBoundaryIdx], heights[i]) - heights[poppedIdx]가 됩니다.
    • 빗물이 고이는 너비 w는 i - leftBoundaryIdx - 1입니다.
    • h * w를 총 빗물 양에 더합니다.
    이 과정을 현재 기둥이 스택 최상단보다 작거나 같아질 때까지 반복한 후, 현재 인덱스 i를 스택에 푸시합니다. 
int trapMonotonicStack(const std::vector<int>& heights) {
    int totalTrappedWater = 0;
    std::stack<int> barStack; // 인덱스를 저장하는 단조 스택

    for (int i = 0; i < heights.size(); ++i) {
        // 현재 기둥의 높이가 스택 최상단 기둥보다 높으면 빗물 계산
        while (!barStack.empty() && heights[i] > heights[barStack.top()]) {
            int poppedBarIdx = barStack.top(); // '골짜기'의 바닥이 되는 기둥
            barStack.pop();

            if (barStack.empty()) { // 스택이 비었으면 왼쪽 벽이 없으므로 빗물 고이지 않음
                break;
            }

            int leftBoundaryIdx = barStack.top(); // '골짜기'의 왼쪽 벽
            // 빗물이 고이는 높이: 왼쪽 벽과 오른쪽 벽 중 낮은 것 - 바닥 기둥의 높이
            int waterHeight = std::min(heights[leftBoundaryIdx], heights[i]) - heights[poppedBarIdx];
            // 빗물이 고이는 너비: 오른쪽 벽 인덱스 - 왼쪽 벽 인덱스 - 1
            int waterWidth = i - leftBoundaryIdx - 1;
            
            totalTrappedWater += waterHeight * waterWidth;
        }
        barStack.push(i); // 현재 기둥 인덱스 스택에 푸시
    }
    return totalTrappedWater;
}

5. 히스토그램에서 가장 큰 직사각형

n개의 음이 아닌 정수가 주어지며, 각각 너비 1인 히스토그램의 막대 높이를 나타냅니다. 이 히스토그램 내에서 그릴 수 있는 가장 큰 직사각형의 면적을 찾는 문제입니다.

해결 전략: 이 문제도 여러 가지 방법으로 해결할 수 있습니다.

  • 브루트 포스: 각 막대를 순회하며, 해당 막대를 포함할 수 있는 가장 큰 직사각형을 찾습니다. 이를 위해 각 막대에서 좌우로 현재 막대보다 낮은 막대를 만날 때까지 확장하여 너비를 계산하고 면적을 구합니다. 모든 가능한 직사각형 중 최댓값을 선택합니다.
  • 동적 계획법(전처리): 빗물 트랩 문제의 DP 해결책과 유사하게, 각 막대에 대해 "자신보다 왼쪽에 있는 첫 번째로 낮은 막대의 인덱스"와 "오른쪽에 있는 첫 번째로 낮은 막대의 인덱스"를 미리 계산하여 저장합니다. 이 정보들을 사용하여 각 막대가 만들 수 있는 최대 너비를 효율적으로 찾고 면적을 계산합니다.
  • 단조 스택: 단조 스택은 이 문제를 효율적으로 해결하는 강력한 방법입니다. 스택에는 막대의 인덱스를 저장하며, 스택은 단조 증가(탑부터 바닥으로 갈수록 감소)를 유지하도록 관리합니다.
    • 배열을 순회하면서 현재 막대 heights[i]를 처리합니다.
    • 스택이 비어있거나 현재 막대가 스택 최상단의 막대보다 크면, 현재 인덱스 i를 스택에 푸시합니다.
    • 현재 막대가 스택 최상단의 막대보다 작으면, 스택 최상단의 막대(h)를 팝합니다. 이때 h를 높이로 하는 직사각형의 너비를 계산합니다. 너비는 팝된 후의 새 스택 최상단(left_boundary_idx)과 현재 인덱스 i를 사용하여 i - left_boundary_idx - 1로 계산됩니다. 이 면적을 최대 면적과 비교하여 업데이트합니다. 이 과정을 현재 막대가 스택 최상단보다 크거나 같아질 때까지 반복한 후, 현재 인덱스 i를 스택에 푸시합니다.
    • 모든 막대를 처리한 후 스택에 남아있는 막대들에 대해서도 위와 유사한 방식으로 너비를 계산하여 면적을 구합니다. 이 경우 오른쪽 경계는 배열의 끝 인덱스 (N)가 됩니다.
    빗물 트랩과 유사하지만, "왼쪽/오른쪽으로 가장 높은 벽"이 아니라 "현재 막대보다 낮은 첫 번째 막대"를 찾아 너비를 결정하는 것이 핵심 차이입니다.

태그: 스택 큐 단조스택 단조큐 자료구조

7월 25일 13:02에 게시됨

인기 태그

©2026 괴물 클럽