[ 백준-17298번 / 스택 ] 오큰수

1. 문제

---

오큰수 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

512 MB

4554

1424

1100

34.472%

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

예제 입력 1 복사

4 3 5 2 7

예제 출력 1 복사

5 7 7 -1

예제 입력 2 복사

4 9 5 4 8

예제 출력 2 복사

-1 8 8 -1

 

 

 

2. 소스코드

---

/* 이전 ver

#include <iostream>
#include <stack>

using namespace std;

stack<int> str, temp, ans;
int n;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;

	while (n--)
	{
		int num;
		cin >> num;
		str.push(num);
	}

	temp.push(str.top());
	str.pop();
	ans.push(-1);

	while (!str.empty())
	{
		if (str.top() < temp.top()) {
			ans.push(temp.top());
			temp.push(str.top());
			str.pop();
		}
		else {
			while (!temp.empty()) {
				temp.pop();
				if (!temp.empty()) {
					if (str.top() < temp.top()) {
						ans.push(temp.top());
						temp.push(str.top());
						str.pop();
						break;
					}
				}
				else {
					ans.push(-1);
					temp.push(str.top());
					str.pop();
					break;
				}
			}
		}
	}

	while (!ans.empty()){
		cout << ans.top() << " ";
		ans.pop();
	}
	return 0;
}
*/

#include <iostream>
#include <vector>
#include <stack>
//#define SIZE 1000000

using namespace std;

stack <int> temp;
//vector<int> input(SIZE), ans(SIZE);

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
    
    vector<int> input(n), ans(n);

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

	temp.push(0);
	for (int i = 1; i < n; i++) {
		while (!temp.empty() && input[temp.top()] < input[i]) {
			ans[temp.top()] = input[i];
			temp.pop();
		}
		temp.push(i);
	}

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

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