[Algorithm] Baekjoon 17298번 : 오큰수

https://www.acmicpc.net/problem/17298

17298번: 오큰수

struct Node
{
    int num; 
    int index;
};
 
int n, input;
 
vector<Node> v;
stack<Node> ms;
vector<Node> indexArr;
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> input;
        v.push_back({ input,i });
    }
 
    for (int i = v.size() - 1; i >= 0; --i)
    {
        Node cur = v[i];
 
        if (ms.empty())
        {
            ms.push(cur);
            indexArr.push_back(cur);
        }
        else
        {
            while (!ms.empty() && ms.top().num <= cur.num)
            {
                ms.pop();
            }
 
            if (ms.empty())
            {
                ms.push(cur);
                indexArr.push_back(cur);
            }
            else
            {
                indexArr.push_back(ms.top());
                ms.push(cur);
            }
        }
    }
 
    reverse(indexArr.begin(), indexArr.end());
 
    for (int i = 0; i < indexArr.size(); ++i)
    {
        int num = indexArr[i].num;
 
        if (i == indexArr[i].index)
        {
            num = -1;
        }
 
        printf("%d ", num);
    }
}

이전문제에서 배웠던 개념인 모노토닉 스택을 이용하여 해결한 문제이다.

오큰수..라는 숫자를 구하는건데 결국 주어진 수열에서 특정숫자를 기준으로 오른쪽으로 가다가 처음으로 특정숫자를 '초과'하는 숫자를 구하는 문제이다.

 

이전문제에서는 '이상'이기에 모노스톤 스택에서 pop할 때 같은값을 안빼줬지만, 이번문제에선 '초과'이기 때문에 같은값도 같이 빼주면 된다. 이부분 빼고는 사실 동일한 문제.

 

 

========== ========== ========== ========== ========== ========== ========== ==========

 

옥상정원과 마찬가지로 굳이 어려운 모노토닉개념을 적용했었다.

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
 
using namespace std;
 
 
int n;
int arr[1000001] = { 0 };
int results[1000001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    memset(results, -1, sizeof(results));
    stack<int> s;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
 
        while (!s.empty() && arr[i] > arr[s.top()])
        {
            results[s.top()] = arr[i];
            s.pop();
        }
 
        s.push(i);
    }
   
 
    for (int i = 0; i < n; ++i)
    {
        printf("%d ", results[i]);
    }
}
 
 

 

 

값들을 입력받은것마다, 스택의 top 인덱스에 해당하는 값이 입력받은값보다 '작다면', 해당 인덱스의 오큰수가 현재 입력값이 된다.

그러니 results에 기록해주고, 스택의 top값인 인덱스에 해당하는 숫자는 오큰수를 구했으니 바로 pop해준다.