[백준] 17298 - 오큰수

1. 문제 이해

하나의 수열이 주어지면, 각 수열의 숫자의 '오큰수' 를 구하는 문제이다.

오큰수란?
자신의 오른쪽에 있는 숫자 중 자신보다 크면서, 그 중 가장 왼쪽에 있는 숫자를 의미한다. 오큰수가 존재하지 않으면 -1 이다.

수열의 크기가 4인 경우, 각 숫자의 오큰수를 순서대로 출력하는 문제이다.

---

2. 문제 풀이

수열의 크기가 최대 1,000,000 이므로, O(N^2) 의 풀이로 풀 수가 없다. 즉, 최대한 선형 시간 만큼의 시간이 걸리도록 알고리즘을 작성해야 한다.

만약 예제가 [9, 5, 4, 7] 이라면 오큰수는 순서대로 (-1, 8, 8, -1) 이다.
이 때, 숫자5는 자신보다 작은 숫자 4를 알 필요가 없다. 마찬가지로 숫자 9는 숫자 4를 알 필요가 없다. 왜냐하면 이미 5라는 숫자가 있기 때문이다.

자신보다 큰 숫자 중 가장 왼쪽에 있는 것을 구해야 하기 때문에 오른쪽 부터 탐색하면서 큰 숫자만 알고있으면 된다. 즉, 오름차순으로 알고있으면 된다. 숫자를 오름차순으로 유지하기 위해서는 스택을 이용한다. 오름차순으로 저장하기 때문에 스택의 Top에 있는 수와 비교하면서 스택의 Top이 오큰수가 되도록 Pop해주면 된다. 이 때, 스택이 비여질 경우 오큰수는 -1이 된다.

현재 보고있는 수를 4라고 해보자

현재 보고 있는 수를 4라고 해보자. 4 오른쪽에는 1 6 5라는 숫자가 있다.

만약 스택에 1 6 5가 들어가있다면 4와 1의 오큰수는 6이다. 자기보다 큰 숫자 중 가장 왼쪽에 있어야 하기 때문에 5는 결국 무시가 된다. 즉, 스택은 Top에 있는 숫자가 가장 작은 숫자로, 오름차순으로 구성되어야 한다.

 

맨 오른쪽 숫자 8을 볼때는 오큰수는 -1이다. 스택에 8울 넣어준다.

그 다음 왼쪽 숫자 4를 볼 때, 4를 넣어줬을 때, 스택이 오름차순이 되도록 만들어준다. 오큰수는 8이고, 스택에 4를 넣어준다.

그 다음 왼쪽 숫자 5를 볼 때, 5을 넣어줬을 때, 스택이 오름차순이 되도록 만들어준다. 그러므로 4 를 빼준다. 오큰수는 8이고 스택에 5를 넣어준다.

그 다음 왼쪽 숫자 3을 보 때, 3을 넣어줬을 때, 스택이 오름차순이 되도록 만들어준다. 오큰수는 5이고 스택에 3를 넣어준다.

정답은 순서대로 출력해야 하므로, 배열에 따로 저장 후 거꾸로 출력해준다.

---

3. 제출 결과

---

4. 문제 코드

#include <stack>
#include <iostream>
#include <vector>
using namespace std;
int num[1000001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    for(int i=0; i<n; i++) { cin >> num[i];}
    stack<int> st;
    vector<int> v; v.push_back(-1);
    st.push(num[n-1]);
    for(int i=n-2; i>=0; i--) {
        while(!st.empty() && st.top() <= num[i]) {
            st.pop();
        }
        if(!st.empty()) {
            v.push_back(st.top());
        } else {
            v.push_back(-1);
        }
        st.push(num[i]);
    }
    int size = v.size();
    for(int i = size-1; i>=0; i--) {
        cout << v[i] << " ";
    }
}