[백준 17298] 오큰수 (C++)

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    vector<int> nums;
    stack<pair<int, int>> s;
    vector<int> answer;
    int input;
    for (int i = 0; i < n; i++) {
        cin >> input;
        nums.push_back(input);
        answer.push_back(-1);
    }

    for (int i = 0; i < n; i++) {
        while (!s.empty() && s.top().second < nums[i]) {
            answer[s.top().first] = nums[i];
            s.pop();
        }

        s.push(make_pair(i, nums[i]));
    }

    for (int i = 0; i < n; i++) {
        cout << answer[i] << " ";
    }
    return 0;
}

어제의 <옥상 정원 꾸미기> 문제를 공부한 것이 많은 도움이 되었다. 이 문제도 마찬가지로 모노톤 스택을 이용하면 간단히 해결되는 문제였다.

먼저, nums 벡터에 입력값들을 전부 담고 동시에 결과를 저장할 answer 벡터에 -1을 넣어주었다. 이렇게 하면 입력을 저정하는 벡터의 크기와 정답을 저장하는 벡터의 크기가 동일하게 유지되어 메모리 낭비를 줄일 수 있을 것으로 생각했기 때문이다.
또, 문제 해결 로직에 필요한 스택 s에 key-value 쌍으로 i와 nums[i] 값을 넣기로 하였다. 이 스택에서 key를 활용하여 결과 벡터에 쉽게 접근할 수 있으며, value를 통해 쉽게 값을 비교할 수 있었다.

그 이후로 nums 벡터를 순회하며 각 nums 값들을 s스택에 쌓아주어야하는데, 그 전에 s의 top()의 value보다 현재 nums[i]의 값이 크다면 오큰수의 조건인 A$_i$의 오큰수는 오른쪽에 있으면서 A$_i$보다 큰 수 중에서 가장 왼쪽에 있는 수를 만족하게 되므로 -1값만 들어있는 answer[i]에 nums[i]의 값을 넣으면서 s 스택의 top을 pop하면 된다. 스택이 비어있거나 의 top()의 value보다 현재 nums[i]의 값이 작지 않으면 이 과정을 반복하다 s에 지금의 nums[i]를 축적하는 것이다. 이것이 가능한 이유는 모노톤 스택은 오름차/내림차순으로 스택의 값들이 정렬된 상태가 유지되는 원리 덕분이다.