[백준] 17298 - 오큰수, C++

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

17298번: 오큰수

 본 문제는 입력의 크기가 1,000,000이므로 O(n^2)의 연산으로 해결할 수 없다. 따라서, 다른 방법으로 해결해야 하는데 stack을 이용해야 한다. stack을 사용해야 된다는 것은 알았는데, 어떻게 사용해야 할지 도저히 감이 잡히지 않았다. 정답을 보고 해결하였는데 stack에 index를 저장해야 한다.

1. stack에 index를 저장
2. index에 해당하는 배열보다 큰 배열의 값이 있을 경우
3. 정답 배열의 index 번째에 저장하고 stack pop
4. 없을 경우 stack에 index 저장
5. stack이 empty가 아닐 때 stack top의 index 번째 정답 배열에 -1 입력
6. 정답 배열 출력

#include <cstdio>
#include <stack>
 
using namespace std;
 
int main() {
    int d[1000000];
    int ans[1000000];
    int t;
    
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        scanf("%d", &d[i]);
    }
    
    stack<int> st;
    st.push(0);
    for (int i = 1; i < t; i++) {
        if (st.empty()) st.push(i);
        while (!st.empty() && d[st.top()] < d[i]) {
            ans[st.top()] = d[i];
            st.pop();
        }
        st.push(i);
    }
    while (!st.empty()) {
        ans[st.top()] = -1;
        st.pop();
    }
    for (int i = 0; i < t; i++) {
        printf("%d", ans[i]);
        if (i != t-1) printf(" ");
    }
    printf("\n");
    return 0;
}