문제

백준 알고리즘 17298번

코드

시간 초과(이중 반복문)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    vector<int> v;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        v.push_back(t);
    }
    for (int i = 0; i < n; i++) {
        int j = i;
        bool check = false;
        while (j < n) {
            if (v[i] < v[j]) {
                cout << v[j] << ' ';
                check = true;
                break;
            }
            j++;
        }
        if (!check)
            cout << -1 << ' ';
    }
    return 0;
}

맞은 코드(스택 사용)

#include <iostream>
#include <stack>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    stack<int> s;
    int* num = (int*)malloc(sizeof(int) * n);
    int* ans = (int*)calloc(n, sizeof(int));
    for (int i = 0; i < n; i++)
        cin >> num[i];
    for (int i = 0; i < n; i++) {
        if (s.empty())
            s.push(i);
        while (!s.empty() && num[s.top()] < num[i]) {
            ans[s.top()] = num[i];
            s.pop();
        }
        s.push(i);
    }
    for (int i = 0; i < n; i++) {
        if (ans[i] == 0)
            cout << -1 << ' ';
        else
            cout << ans[i] << ' ';
    }
    free(num); free(ans);
    return 0;
}

n이 커지니 이중 반복문은 시간 초과가 발생했다. 스택 문제인걸 몰랐다면 시간 초과를 어떻게 해결해야할지 정말 막막했을 것 같다ㅠㅠ.. 좀 더 노력해서 공부해야지!