[백준 17298] 오큰수 C++

문제

백준 17298 오큰수 C++

17298번: 오큰수

풀이

스택을 활용합니다.

처음에는 미리 입력을 스택에 다 넣어주고, 하나씩 꺼내면서 비교했는데, 이 경우에는 최악의 경우 (내림차순으로 정리되어 있을 때) O(n^2)의 시간 복잡도를 가지기 때문에 n이 백만이나 될 수 있는 해당 문제에는 시간 초과가 발생합니다.

따라서 입력을 줄 때 바로 결과를 도출할 수 있게 시간복잡도를 O(n)까지 줄여야 합니다.

 

1. 원소(num)를 입력을 받습니다.

2-1. 스택이 비어 있다면, 원소의 index를 스택에 push해 줍니다.

2-2. 스택이 비어있지 않다면, 스택의 Top의 해당하는 원소(arr[idx], 여기서 idx = st.top())와 비교합니다.

1) num이 원소보다 크다면 num이 해당 원소의 오큰수가 됩니다. arr[idx]에 num을 넣어주고 Pop 해 줍니다.

2) 그렇지 않다면 다음 원소와 비교해야 합니다. 스택에 원소의 index를 push 해주고 break를 걸어 다음 원소와 비교합니다.

3. N만큼 반복합니다. 이 때 오큰수가 없는 수의 index들은 스택에 저장되어있습니다.

4. 스택이 빌 때까지 index를 꺼내주면서, index에 해당하는 원소를 -1로 바꿔줍니다. (오큰수가 없으므로)

5. 오큰수를 출력합니다.

 

예제 입력 2번으로 실행했을 때 결과입니다.

첫 번째 입력으로 9를 받았을 때, 스택이 비어 있으므로 원소의 idx인 0을 스택에 push 해 줍니다.

두 번째 입력으로 5를 받았을 때, num(5와 같습니다)이 arr[st.top()] (9와 같습니다) 보다 작으므로 index인 1을 스택에 push 해 줍니다.

세 번째 입력으로 4를 받았을 때, num(4와 같습니다)이 arr[st.top()] (5와 같습니다) 보다 작으므로 index인 2를 스택에 push 해 줍니다.

네 번째 입력으로 8을 받았을 때, num(8과 같습니다.)이 arr[st.top()] (4와 같습니다) 보다 크므로 arr[2]를 num으로 바꿔주고 스택을 pop 해줍니다. 계속해서 반복합니다.

num(8과 같습니다.)이 arr[st.top()] (5와 같습니다) 보다 크므로 arr[1]를 num으로 바꿔주고 스택을 pop 해줍니다. 계속해서 반복합니다.

num(8과 같습니다)이 arr[st.top()] (9와 같습니다) 보다 작으므로 index인 3을 스택에 push 해 줍니다.

입력이 이제 더 이상 없습니다. 스택을 비워주면서 index에 해당 하는 원소에 -1을 넣어줍니다. 스택에 0, 3이 있었으므로 arr[0], arr[3]에 -1을 넣습니다.

따라서 오큰수는 -1 8 8 -1입니다.

소스 코드

#include <iostream>
#include <stack>
using namespace std;
 
int arr[1000001];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int N;
    cin >> N;
    stack<int> st;
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        arr[i] = num;
        while (1) {
            // 스택이 비었으면 바로 push
            if (st.empty()) {
                st.push(i);
                break;
            }
            // 스택이 비지 않았으면 스택의 Top과 비교
            int idx = st.top();
            // num이 더 클 경우에는 index에 해당하는 원소에 num을 넣어주고 Pop
            if (num > arr[idx]) {
                arr[idx] = num;
                st.pop();
            }
            // num이 작거나 같으면 스택에 push하고 다음 원소 확인
            else {
                st.push(i);
                break;
            }
        }
    }
    // 스택에 남아 있는 index들에 해당하는 원소는 더 큰 수가 없으므로 -1을 넣어줌
    while (!st.empty()) {
        int idx = st.top();
        arr[idx] = -1;
        st.pop();
    }
    // 오큰수들 출력
    for (int i = 0; i < N; i++) {
        cout << arr[i] << ' ';
    }
    return 0;
}