[BOJ]17298번: 오큰수(c++)

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

17298번: 오큰수

 

 

#include <iostream>
#include <stack>
#include <vector>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // 입력
    int n;
    cin >> n;
    vector<int> input(n);
    for (int i = 0; i < n; i++)
    {
        cin >> input[i];
    }
 
    // 스택: 오큰수를 아직 찾지 못한 수
    stack<int> yet;
    yet.push(0);
 
    // 오큰수 찾기
    vector<int> nge(n);
    for (int i = 1; i < n; i++)
    {
        // input[i]가 top의 오큰수이면
        while (!yet.empty() && input[yet.top()] < input[i])
        {
            nge[yet.top()] = input[i];
            yet.pop();
        }
        yet.push(i);
    }
 
    // 오큰수를 찾지 못한 수 처리
    while (!yet.empty())
    {
        nge[yet.top()] = -1;
        yet.pop();
    }
 
    // 출력
    for (int i = 0; i < n; i++)
    {
        cout << nge[i] << ' ';
    }
 
    return 0;
}

 

 

TIP1

왜 스택을 사용해야 하나?

// 이중포문..O(n^2) 시간초과가 났다
vector<int> NGE(n);
for (int i = 0; i < n; i++)
{
    NGE[i] = -1;
    for (int j = i + 1; j < n; j++)
    {
        if (input[j] > input[i])
        {
            NGE[i] = input[j];
            break;
        }
    }
}

 

이중포문을 돌려도 답안이 나온다.

하지만 시간초과 때문에.. 속도를 위해 스택을 사용해야 한다는 결론

 

 

TIP2

스택에 넣을 수의 기준을 잡자. 

1. "오큰수를 아직 찾지 못한 수"를 스택에

2. "오큰수"를 스택에

 

2가지가 있다. 

나는 1번으로 문제를 풀었는데, BOJ의 상위 답안들은 2번으로 문제풀이를 했다.

2번으로 풀려면 for문을 뒤에서부터 돌려야 한다.

(오등큰수 문제풀이 참고)