[c++] 백준 17298 - 오큰수(스택)

0. [c++] 백준

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

1. 풀이

뒤에서 부터 스택에 수를 집어넣어준다.

스택은 내림차순으로 유지되도록 하였다.

i번 차례에서 자신보다 큰 수가 나올 때 까지 pop을 해주고 이 stk이 비어있는지 확인을 해준다.

비어있으면 오큰수가 존재하지 않는 것이므로 ret에 -1을 넣고, 아닌경우 stk.top()을 넣어준다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include<iostream> #include<algorithm> #include<deque> #include<vector> #include<stack>   using namespace std;   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       int N;     cin >> N;     vector<int> V(N), ret(N);     stack<int> stk;       for (int i = 0; i < N; i++)         cin >> V[i];       for (int i = N - 1; i >= 0; i--) {         while (!stk.empty() && stk.top() <= V[i])             stk.pop();           if (stk.empty())             ret[i] = -1;         else             ret[i] = stk.top();           stk.push(V[i]);     }     for (auto a : ret)         cout << a << " "; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!