백준 17299 오등큰수

문제링크

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

문제

풀이

1. 각 숫자가 몇번 등장하는지 cnt 배열을 통해 카운트를 해준다.

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

2. for문을 통해 arr 배열의 뒤에 있는 숫자부터 접근을 한다.
   먼저 배열의 가장 뒤에있는 숫자를 스택에 담아준다.
   

3. 이후에는 반복문을 돌며 스택에 있는 숫자중 현재 배열에 있는 숫자보다 등장 횟수가 적거나 같은 숫자를 모두 pop해준다.

	while(!st.empty()){
		if(cnt[arr[i]]>=cnt[st.top()]) st.pop()
		else break;
    	}

4. 스택의 top에 있는 숫자를 ans에 push 해준다.스택이 비어있다면 현재 숫자보다 등장 횟수가 많은 숫자가 없는 것이므로 ans에 -1을 push 해준다.

		if (st.empty()) ans.push(-1);
		else ans.push(st.top());

5. 스택에 현재의 숫자를 push 해준다.

6. 반복

코드

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

stack<int> st,ans;
int arr[1000001];
int cnt[1000001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

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

	for (int i = n-1; i >= 0; i--) {

		while (!st.empty()) {
			if (cnt[arr[i]] >= cnt[st.top()]) st.pop();
			else break;
		}
		
		if (st.empty()) ans.push(-1);
		else ans.push(st.top());
		st.push(arr[i]);
		
	}

	while (!ans.empty()) {
		cout << ans.top() << ' ';
		ans.pop();
	}
}

후기

고민하다 알고리즘 분류에 스택이 적혀있는것을 보고 힌트를 얻어 풀었다. 아쉽다.