[백준 17298번] 오큰수

[백준 17298번] 오큰수

www.acmicpc.net/problem/17298

17298번: 오큰수

 

 

 문제

 크기가 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)을 공백으로 구분해 출력한다.

 

 

 풀이

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int N;
	cin >> N;
	vector<int> temp;
	stack<int> val;
	stack<int> result;
	for(int i=0;i<N;i++){
		int a;
		cin >> a;
		temp.push_back(a);
	}
	
	val.push(temp.back());
	result.push(-1);
	for(int i=temp.size() - 2;i>=0;i--){
		if(val.top() > temp[i]){
			result.push(val.top());
			val.push(temp[i]);
		}
		else{
			bool flag = false;
			while(val.top() <= temp[i]){
				val.pop();
				if(val.empty()){
					result.push(-1);
					val.push(temp[i]);
					flag = true;
					break;
				}
			}
			if(!flag){
				result.push(val.top());
				val.push(temp[i]);
			}
		}
	}
	
	while(!result.empty()){
		cout<< result.top() << ' ';
		result.pop();
	}
	return 0;
}

문제를 보고 처음 떠올랐던 생각은 완전탐색이었지만 완전 탐색의 경우 시간복잡도가 O(n^2)로 입력이 1000000이기 때문에 시간초과가 예상되었다. 어떻게 풀지 고민하다가 monotone stack이라는 개념을 공부하게 되었다.

 

배열의 맨뒤에서 부터 차례대로 스택에 넣으면서 스택이 감소하는 형태를 유지하도록 하는 것이다. 예를 들어 3, 5, 2, 7로 설명하자면 먼저 7이 스택에 들어간다. 다음은 2이고 2는 스택의 top인 7보다 작기 때문에 그대로 스택에 들어간다. 다음은 5이고 5는 스택의 top인 2보다 크기 때문에 스택에서 pop을 하고 다시 top과 비교한다. 스택의 top은 7이므로 5는 스택에 들어온다. 다음은 3이고 3은 스택의 top인 5보다 작기 때문에 스택에 들어온다.

 

이런 과정을 거치면서 스택에 값이 들어오기 직전의 top이 문제에서 요구하는 정답이기 때문에 따로 모아서 출력하면 된다.