[C++] 백준 17298번 오큰수

1) 문제설명

백준 Online Judge 17298번 오큰수

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

17298번: 오큰수

 

2) 해결방법

 

배열의 오른쪽 부터 스택에 넣고 스택의 값과 배열의 값을
비교하여 새로운 배열에 큰 수를 집어 넣는다.

 

 

3) 코드

#include<iostream>
#include<queue>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;


long long arr[1000001];
long long brr[1000001];
/*
오큰수
해결방안
배열의 오른쪽 부터 스택에 넣고 스택의 값과 배열의 값을
비교하여 새로운 배열에 오큰수를 집어 넣는다.

*/
int main() {
	int n;
	
	stack<long long> s;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	for (int i = n-1;i >= 0; i--) {
		if (s.empty()) { // 스택이 비었다면 brr에 -1을 넣고 스택에 값을 넣는다
			s.push(arr[i]);
			brr[i] = -1;
		}
		else if (arr[i] < s.top()) { // 입력값보다 스택 값이 더 크다면 brr에 스택 값을 넣고
			brr[i] = s.top();
			s.push(arr[i]); // 스택에 입력값을 넣는다.
		}
		else if (arr[i] >= s.top()) { // 입력값이 스택 값 보다 크다면
			while (1) {
				
				if (s.empty()) { // 스택이 비었다면 
					brr[i] = -1; // brr에 -1을 넣고
					s.push(arr[i]); // 스택에 입력값을 넣는다.
					break;
				}
				else if (arr[i] >= s.top()) { // 입력값이 스택보다 크다면
					s.pop(); // 스택 값을 뺀다
				}
				else { // 입력값이 스택보다 작다면
					brr[i] = s.top(); // brr에 스택 값을 넣고
					s.push(arr[i]); // 스택에 입력값 추가
					break;
				}
			}
		}
	} 
	for (int i = 0; i < n; i++) {
		cout << brr[i] << ' ';
	}
}