-
17298) 오큰수 c++백준코딩일기 2020. 11. 19. 16:57
문제 ) www.acmicpc.net/problem/17298
풀이 )
Monotone stack 을 이용하는 문제였다.
입력받은 배열의 맨 뒤부터 스택에 넣어주고, 스택을 감소하는 상태로 유지하면서 비교한다.
-1 을 처리해주기 위해서 처음에 스택에 infinity(무한대) 값을 넣는다.
-> s.push(1e9+7);1e9 = 1*109 = 1,000,000,000
코드 )
#include <iostream> #include <stack> #include <vector> using namespace std; int n; stack<int> s; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; vector<int> v(n), ans(n); for(int i=0; i<n; i++) cin >> v[i]; s.push(1e9+7); for(int i=n-1; i>=0; i--){ while(s.top() <= v[i]) s.pop(); if(s.top() >= 1e9) ans[i] = -1; else ans[i] = s.top(); s.push(v[i]); } for(auto i : ans) cout << i << " "; }
'백준코딩일기' 카테고리의 다른 글
10820) 문자열 분석 c++ (0) 2020.11.24 10809) 알파벳 찾기 c++ (0) 2020.11.23 9093) 단어 뒤집기 c++ (0) 2020.11.19 4889) 안정적인 문자열 c++ (0) 2020.11.17 2504) 괄호의 값 c++ (0) 2020.11.17