BOJ 17299] 오등큰수

[ 접근법 ]

- 오큰수 문제와의 차이점이라면 등장 횟수를 추가로 저장해야한다는 것이다.

- 등장 횟수를 따로 저장하는 것 이외에 그대로 진행하면 된다.

 

[ 주의 사항 ] 

- 등장횟수와 값을 저장하는 배열 두가지를 혼동하지 말자.

- stack과 결과값에는 순서를 저장해두자!

 

[ 코드 ]

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

using namespace std;


stack<int> s;
int arr[1000001]; //num[i]의 등장횟수
int num[1000001]; //i번째 원소의 값
int res[1000001]; //v에는 오등큰수의 순서가 정리

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

	cin >> n;
	for (int i = 0; i < n;i++) {
		cin >> temp;
		
		num[i] = temp;
		arr[num[i]]++; //arr[0] = 0의 등장횟수
	}

	// num[i] = i번째 원소의 값
	// arr[num[i]] = i번째 원소의 등장횟수
	// s = i번째 원소
	// res[i] = i번째 원소의 오등큰수
	// s.top = i번째 원소

	for (int i = 0; i < n; i++) {
		while (!s.empty() && arr[num[s.top()]] < arr[num[i]]) {
			//cout << "arr[top] : " << arr[num[s.top()]] << ", arr[i] : " << arr[num[i]] << endl;
			//cout << "top : " << num[s.top()] << ", i : " << num[i] << endl;
			res[s.top()] = num[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;
}