17298 오큰수

문제

• 수열A가 주어졌을 때 각각의 원소 A_i에 대하여 오른쪽에 있으면서 A_i보다 큰 수 중에서 가장 왼쪽에 있는 수를 구하는 문제이다.

입력

• 수열의 크기 N
• 수열 A의 원소가 둘째 줄에 주어진다.

출력

• 각원소 A_i의 오큰수를 각각 출력하고 오큰수가 없다면 -1출력

---

10
10 1 9 2 8 3 7 4 6 5

이라는 예제가 주어졌다 생각해보자.
오른쪽에서 하나씩 확인하면

• 10 > 1 (오큰수아님)
• 10 > 9 (오큰수아님)
  ...
• 10 > 5 (오큰수아님)이므로

10의 출력은 -1이다. 이렇게 한 후에 다시 두 번째 원소인 1로 돌아간다면 시간복잡도가 O(N^2)이므로 이 방법은 안된다.
원소를 지나칠 때마다 지나친 원소는 A_i > A_i+1이라는 특성을 이용하는 것이 핵심 방법이다.

• 10 > 1
• 1 < 9 (오큰수 발견)
• 10 < 9 (오큰수 아님)
• 9 > 2
• 2 < 8 (오큰수 발견)
• 9 > 8 (오큰수 아님)
  ...

이런식으로 그 전에 있던것들 중 가장 위에있는 원소를 한번씩 확인하면 시간복잡도를 크게 줄일 수 있다.
제일 처음 넣은 원소가 제일 마지막에 비교되므로 이 방법은 스택을 이용한다.

---

정답코드

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

using namespace std;

queue<int>arr; // 맨 앞에서부터 하나씩 빠져나오는 구조이므로 큐 이용
stack<pair<int, int>>temp; // 오큰수를 발견하지 못한 수를 담을 공간
int answer[1000000]; // 답을 담을 공간


void sol() {
	int i = 0;
	temp.push(make_pair(i,arr.front()));
	arr.pop();
	while (!arr.empty()) {
		i++;
		if (!temp.empty()) {
			while (!temp.empty() && temp.top().second < arr.front()) {
				answer[temp.top().first] = arr.front();
				temp.pop();
			}
		}
		temp.push(make_pair(i,arr.front()));
		arr.pop();
	}
	while (!temp.empty()) {
		answer[temp.top().first] = -1;
		temp.pop();
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int cup;
		cin >> cup;
		arr.push(cup);
	}
	sol();
	for (int i = 0; i < n; i++) {
		cout << answer[i] << ' ';
	}

	return 0;
}