[백준 C++] 17299번: 오등큰수

https://www.acmicpc.net/problem/17299

17299번: 오등큰수

 

전에 풀었던 17298 오큰수랑 비슷한 문제이다.

 

이것도 큰수중에서 가장 왼쪽에 있는 수를 출력해야 하므로 stack을 사용하였다.

 

#include <iostream>
#include <stack>
using namespace std;
int a[1000001] = { 0, };
int f[1000001] = { 0, };
int ans[1000001] = { 0, };
stack<int> s;
 
int main() {
	int n;
	cin >> n;
	for (int i = 0;i < n;i++) {
		cin >> a[i];
		f[a[i]]++;
	}
	
	for (int i = n - 1;i >= 0;i--) {
		while (!s.empty() && f[s.top()] <= f[a[i]]) {
			s.pop();
		}
 
		if (s.empty()) {
			ans[i] = -1;
		}
		else {
			ans[i] = s.top();
		}
		s.push(a[i]);
	}
 
	for (int i = 0;i < n;i++) {
		cout << ans[i] << ' ';
	}
 
	return 0;
}

 

간단하게 int f 배열 추가해주고 대소비교를 f[i]로 하게끔 바꾸어서 문제를 풀었다.