오큰수 //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이다.
  
  
  //시간제한: 1초 , 메모리: 512MB

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

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

---

// Created by dongwan-kim on 2022/07/22.
#include<iostream>
#include<stack>

using namespace std;

int n, m;
stack<int> s;
stack<int> p;
stack<int> ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> m;
        s.push(m);
    }

    while (!s.empty()) {
        while (!p.empty() && s.top() >= p.top()) {
            p.pop();	//큰수를 만날때까지 Pop
        }
        if (p.empty()) {	//오른쪽에 큰 수가 없을 경우
            ans.push(-1);
            p.push(s.top());
            s.pop();
        } else {		//p.top이 오큰수 일 때
            ans.push(p.top());
            p.push(s.top());
            s.pop();
        }
    }

    while (!ans.empty()) {		//정답 출력
        cout << ans.top() << " ";
        ans.pop();
    }
}

---

풀이

스택을 사용하여 문제를 해결했다.
자신 숫자 기준으로 오른쪽에 있는 수들을 비교해야 하므로 마지막 입력받은 수부터 진행해야 효율적이기 때문에
입력받는 수들을 s스택에 넣어 비교하며 오큰수를 ans에 담는 방식으로 구현하였다.

자신보다 높은 숫자가 나올때까지, 즉 자신의 오큰수를 만날때까지 while을 돌리며 작은 숫자들을 pop해주었고, 만약 전부 pop되어 p스택이 비어있게 될 경우 ans에 -1을 push하였다. 비어있지 않은 경우에는 p.top을 ans스택에 push하도록 했다.

처음 문제를 풀 때 p스택에서 오큰수가 아닌 숫자를 pop해주는 부분에서
pop하는 숫자들을 계속 가지고 있어야 뒤에 숫자들을 비교할 때 예외가 없을 것이라고 생각하여 temp 스택을 하나 더 만들어서 모든 숫자를 관리하고 저장하는 방식으로 구현했었다. 하지만 이런식으로 해서는 시간초과를 피할 수 없다고 생각했고, 다시 생각해보니 오른쪽에서 큰 수 중 가장 왼쪽에 있는 숫자이기 때문에 이전에 오큰수가 아니었던 수를 가지고 있을 필요가 없다는 것을 알게 되었다.

while (true) {
        if (!pop.empty() && s.top() < pop.top()) {
            ans.push(pop.top());
            while (!temp.empty()) {
                pop.push(temp.top());
                temp.pop();
            }
            pop.push(s.top());
            s.pop();
        } else {
            if (!pop.empty()) {
                temp.push(pop.top());
                pop.pop();
            } else {
                ans.push(-1);
                while (!temp.empty()) {
                    pop.push(temp.top());
                    temp.pop();
                }
                pop.push(s.top());
                s.pop();
            }
        }
        if (s.empty())
            break;
    }
    

이 코드로 제출하고 시간초과가 뜬 것을 본 후 생각해보니, 너무 당연하게 시간초과가 발생하는 것을 알 수 있었다. 이번 문제를 통해 입력받은 순서대로 처리하는 것이 아닌 뒤에서부터 처리해주는 사고와, 문제 풀이 전 시간복잡도를 꼭 생각해 보아야한다는 것을 느낄 수 있었다.