[C++] BOJ(백준) 17298 오큰수

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

17298번: 오큰수

 

스택 자료구조 문제다.

 

시간초과가 날 걸 알면서도 단순하게 하나하나 검사하는 방법으로 해봤다.

혹시나 했는데 어림도 없지 시간초과다.

 

뒤에서부터 탐색하여 최댓값들을 저장하는 방법에 대해 생각했다.

그러면 최댓값이 가장 오른쪽에 존재한다는 보장이 없다.

 

지금까지 저장한 오큰수들을 탐색해보려고 했는데

이거는 단순 이중 반복문이나 다름이 없었다.

 

그러다 든 생각은 뒤에서부터 탐색하며 수들을 스택에 넣는 것이다.

스택에 넣게 되면 가장 위에 있는 값이 해당 수 보다 큰 수 중 가장 오른쪽에 있음을 확신할 수 있다.

탐색 중 해당 수가 스택의 맨 위에 있는 값보다 크다면 스택의 값을 제거한다.

 

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

int arr[1000001];
int re[1000001];

stack<int> s;

int main() {
	// 입출력 속도를 단축시키기 위함
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];

	for (int i = n - 1; i >= 0; i--) {
		// 스택에 들어있는 수가 더 작으면 제거
		while (s.size() && arr[i] >= s.top()) s.pop();

		// 스택이 비어있으면 큰 수가 없는 것이므로 -1
		if (s.size() == 0) re[i] = -1;
		// 스택이 차있다면 맨 위에 있는 값이 큰 수 중 가장 오른쪽에 존재
		else re[i] = s.top();

		// 현재 값을 스택에 삽입
		s.push(arr[i]);
	}

	for (int i = 0; i < n; i++) cout << re[i] << " ";
}

(ﾉ◕ヮ◕)ﾉ*:･ﾟ✧