BOJ 17298] 오큰수

[ 접근법 ]

- 오른쪽 수열에서 자신보다 큰 수중 가장 작은 값을 구하는 것이기 때문에 stack을 이용하자.

- 하나하나 비교하는 o(n*n)는 수가 100000에 달하기 때문에 다른 방법을 모색해야 된다.

- 왼쪽에 있는 수열의 오큰수는 무조건 오른쪽의 있는 수열보다 작거나 같다.

- 그렇기 때문에 만약 다음 수열이 자신의 오큰수가 아니라면 stack에 저장해두고 다음 수열의 오큰수가 등장하면,

그때 stack을 pop하면서 해당 오큰수가 stack에 저장된 오큰수가 맞나 확인을 한다.

- 만약 오큰수가 아니라면 -1을 저장한다.

 

[ 주의사항 ]

- 결과 저장배열에 수열 순서대로 저장해야 순서가 뒤죽박죽 되지 않는다.

- 시간이 1초라고 해서 이중반복문이 등장하면 안되는 것이 아니다!

- 마찬가지로 굳이 입력을 한번에 안받도 받는 즉시 하려고 하지 않아도 된다!

- 순서 저장할라고 큐를 도입했는데 그러지말고 배열을 이용해서 순서를 저장해라!

 

 

[ 코드 ]

#include <iostream>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

/*
순서를 저장해야하면 배열을 이용해서 순서를 기록하자!
*/

stack<int> s;
int arr[1000001]; // 순서대로 수열을 저장
int res[1000001]; // 각 수열의 오큰수의 값을 저장

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, temp, num;
	cin >> n;
	num = n;
	

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

	for (int i = 0; i < n; i++) {
		while (!s.empty() && arr[s.top()] < arr[i]) {
			res[s.top()] = arr[i];
			s.pop();
		}
		s.push(i);
	}

	while (!s.empty()) {
		res[s.top()] = -1;
		s.pop();
	}

	for (int i = 0; i < n; i++) {
		cout << res[i] << ' ';
	}
	
	 
	 return 0;
}