[백준 C++] 17298. 오큰수

문제 링크

---

17298번: 오큰수

접근 방법

---

수열의 크기가 최대 1,000,000이므로 brute-force로 찾게 되면 시간 복잡도는 n^2이 되기 때문에 시간초과가 나게 됩니다.

따라서 stack을 사용하여 O(n^2)을 O(n)으로 최적화해서 문제를 해결합니다.

 

소스 코드

---

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

using namespace std;

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

    int n;
    cin >> n;
    vector<int> num(n), answer(n, -1);
    for (auto &a : num)
        cin >> a;

    stack<int> s;
    for (int i = 0; i < n; i++)
    {
        while(!s.empty() && num[s.top()] < num[i])
        {
            answer[s.top()] = num[i];
            s.pop();
        }
        s.emplace(i);
    }

    for (auto &a : answer)
        cout << a << ' ';

    return 0;
}

코드 설명

---

오른쪽에 큰 수가 없을 때 -1을 출력해야 하므로 미리 ans 배열을 -1로 초기화합니다.

스택에는 수열의 인덱스를 넣습니다. 스택의 top 은 항상 i 보다 작은 인덱스입니다.

즉 num[s.top()] < num[i] 를 만족하게 되면 num[s.top()]  보다 오른쪽에 있으면서

num[s.top()] 보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미하게 됩니다. 

 

오큰수를 찾게 되면 해당 인덱스는 더 이상 확인해 줄 필요가 없으므로 pop 해주며

ans 배열에 s.top에 해당하는 인덱스에 오큰수를 넣어줍니다.

그리고 스택에 들어있는 이전 인덱스들에 대해서도 오큰수를 만족하는지 확인합니다.

 

스택이 단조 감소 스택을 만족하기 때문에 스택의 top만 확인해 줍니다.