[BOJ/백준 17298][C++] 오큰등수

문제

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

백준 17298

 

문제 내용

수열이 주어지고, 수열의 각 원소의 오큰등수를 구하면 되는 문제이다.

오큰등수란 자신보다 오른쪽에 있으면서, 자신보다 커야 하며, 그중에서 가장 왼쪽에 있는 수이다.

즉, 자신보다 오른쪽에 있는 수들 중에 가장 가까운 큰 수를 찾으면 되는 문제이다. 

 

문제 풀이

n의 범위가 10^6이기 때문에, 이중 for문으로 돌리면 시간초과가 나게 된다.

그래서 stack을 사용하여 문제를 풀었는데, 수열을 역순으로 탐색하며 문제를 풀면 된다.

기본적으로 모든 원소를 stack에 push하며 나가되, 자신보다 작은 수는 pop을 하고 자신을 push 하는 과정을 진행하면 된다.

 

아래 글에 풀이가 정말 잘 설명이 되어있다.

https://cocoon1787.tistory.com/347

[C/C++] 백준 17298번 - 오큰수 (스택)

 

 

코드

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

using namespace std;

/**
 * 백준 17298 오큰등수
 * 주의사항1: 입력이 10^6개가 들어올 수 있기 때문에, 이중 for문으로 돌면 시간초과가 나는 문제이다.
 * 주의사항2: 수열의 원소가 전부 다르다는 조건이 없기 때문에, pop하는 조건을 체크할 때 주의해야 한다.
 *           (오큰등수는 자신보다 반드시 커야 한다.)
 */

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    stack<int> st;
    vector<int> result(n, 0);

    // 역순으로 체크
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && st.top() <= arr[i]) {
            st.pop();
        }

        if (st.empty())
            result[i] = -1;
        else {
            result[i] = st.top();
        }
        st.push(arr[i]);
    }

    for (auto num : result)
        cout << num << ' ';
}