백준 17298번 - 오큰수(c++)

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

17298번: 오큰수

우선 처음 떠올린 풀이는 이랬다.

#include <bits/stdc++.h>

using namespace std;

int v[1000004];
int result[1000004];

int n;
int temp;
int main() 
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> v[i];
    }

    for(int i = 0; i < n; i++)
    {
        if(i == n-1)
        {
            result[i] = -1;
            break;
        }
        for(int j = i+1; j < n; j++)
        {
            if(v[i] < v[j])
            {
                result[i] = v[j];
                break;
            }

            if(j == n-1)
                result[i] = -1;
        }
    }

    for(int i = 0; i < n; i++)
        cout << result[i] << ' ';

    return 0;
}

여기서 시간 복잡도를 계산해보자.

이중반복문이라 n^2이다.

100만 * 100만 = 1조다. 무려 1조...

도중에 break를 한다해도 최악의 경우는 1조이다. 그래서 해당 경우는 불가하다.

솔직히 여기서부터는 어떻게 해야할지 몰라서 구글링을 했다.

그러던 중 도움을 받은 글을 출처를 남깁니다.

https://cocoon1787.tistory.com/347

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

큰 수를 원하니까 가장 끝에서부터 접근해서 인덱스를 활용해 스택을 활용하는 방법이다.

솔직히 처음 풀어본 입장에서는 이런 풀이는 도저히 못 떠올릴 것 같다.

이런 경우에 스택을 쓴다 정도로 머릿속에 기억해놓고 추후에 코테풀 때 이런 경우에 시간초과일 것 같으면

스택을 사용해보자를 생각해봐야겠다.

#include <bits/stdc++.h>

using namespace std;

int n;
stack<int> s;

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

    cin >> n;
    vector<int> v(n);
    vector<int> ans(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];

    for(int i = n-1; i >= 0; i--)
    {
        while(!s.empty() && s.top() <= v[i])
            s.pop();
        if(s.empty())
            ans[i] = -1;
        else
            ans[i] = s.top();
        
        s.push(v[i]);
    }

    for(auto i : ans)
        cout << i << ' ';
        
    return 0;
}