[c++] 백준 17298: 오큰수

17298번: 오큰수

🟡 문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

🟡 입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

🟡 출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

---

👀 코드

/**
 * baekjoon - 17298
 * stack
 */

#include <iostream>
#include <stack>
#include <vector>
#define fio ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

int main(){
    fio;
    //input
    int n, x;
    vector<int> a;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> x;
        a.push_back(x);
    }

    //sol
    stack<int> s;
    vector<int> result(n);
    for (int i = n - 1; i >= 0; i--){
        while (!s.empty() && s.top() <= a[i]){
            s.pop();
        }

        if (s.empty()) result[i] = -1;
        else result[i] = s.top();

        s.push(a[i]);
    }

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

    return 0;
}

---

📌 해설

해당 문제는 스택을 활용해 해결하는 문제이다. 이중 for문으로 처음 시도하였을 때는 시간 제한이 걸리기 때문에 스택을 잘 활용해야 한다. 또한 오큰수라는 특징을 활용해 오른쪽에서 접근하면 쉽게 풀 수 있다. 오른쪽부터 하나씩 stack에 넣어 저장하면 되는데 이 때, 이미 저장되어 있는 stack의 top값을 비교하여 만약 stack의 top이 현재 접근하고 있는 배열보다 작으면 stack의 top을 pop시켜 정리시켜준다. 그렇게 반복한 후 문제를 해결해주면 된다.

1. n과 배열을 vector를 이용해 입력받는다.

2. 배열을 뒤에서부터 검사하여 비어있지 않으면 해당 배열의 숫자와 비교하여 stack의 top이 배열의 숫자보다 작거나 같다면 스택을 pop해준다. 이 과정을 while문에서 반복하여 stack을 정리해주는 역할을 한다.

3. 2번 작업을 한 후, stack이 empty이라면 현재 자신보다 큰 수는 존재하지 않기 때문에 -1이다.

   따라서 배열에 마지막 숫자는 항상 자신보다 큰 수가 stack에 담겨있지 않기 때문에 -1이 저장되어야 한다.

4. empty가 아니라면 stack의 top이 오큰수이기 때문에 이를 결과에 저장해주면 된다.

5. 마지막으로 결과를 저장한 값을 주어진 출력 형식에 맞춰 출력해주면 된다.