[백준 17299번] 오등큰수

[백준 17299번] 오등큰수

www.acmicpc.net/problem/17299

17299번: 오등큰수

 

 

 문제

 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.

Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.

예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.

 

 입력

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

 

 출력

 총 N개의 수 NGF(1), NGF(2), ..., NGF(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;
	int arr[1000001] = {0,};
	for(int i=0;i<N;i++){
		int a;
		cin >> a;
		temp.push_back(a);
		arr[a]++;
	}
	
	stack<int> val;
	stack<int> result;
	
	val.push(temp.size()-1);
	result.push(-1);
	for(int i=temp.size() - 2;i>=0;i--){
		if(arr[temp[val.top()]] > arr[temp[i]]){
			result.push(temp[val.top()]);
			val.push(i);
		}
		else{
			bool flag = false;
			while(arr[temp[val.top()]] <= arr[temp[i]]){
				val.pop();
				if(val.empty()){
					result.push(-1);
					val.push(i);
					flag = true;
					break;
				}
			}
			if(!flag){
				result.push(temp[val.top()]);
				val.push(i);
			}
		}
	}
	
	while(!result.empty()){
		cout<< result.top() << ' ';
		result.pop();
	}
	return 0;
}

앞서 풀었던 17298번 문제와 같은 맥락의 문제이다. arr 배열을 통해 등장한 횟수를 저장해 두고 monotone stack의 개념을 사용하되 스택에 들어가는 값은 index 값으로 한다. 비교는 해당 index 값으로 temp 벡터의 값을 가져와 다시 arr 배열에서 등장 횟수를 통해 비교한다. 나머지는 17298번과 같다. 17298번 문제에서 약간의 수정을 거치니 맞았습니다를 받을 수 있었다.