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

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

17299번: 오등큰수

 

전체 코드

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int N;
int arr[1000001];
int res[1000001];
stack<pair<int,int>> s; // 번호와 등장횟수
vector<int> v;
void solve()
{
	//첫 시작은 무조건 오큰수가 없음.
	s.push(make_pair(v[N - 1], arr[v[N - 1]]));
	res[N - 1] = -1;

	for(int i = v.size() - 2; i >= 0; i--)
	{
		while (!s.empty() && arr[v[i]] >= s.top().second)
		{
			s.pop();
		}

		if (s.empty())
			res[i] = -1;
		else
			res[i] = s.top().first;
		s.push(make_pair(v[i], arr[v[i]]));
	}

}

int main(void)
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);

	cin >> N;
	int A;
	for (int i = 0; i < N; i++)
	{
		cin >> A;
		arr[A]++;
		v.push_back(A);
	}
	solve();
	for (int i = 0; i < N; i++)
		cout << res[i] << " ";
}

음... 풀이 방법은 맨 오른쪽의 수부터 차례대로 왼쪽으로 스택에 넣을 것입니다.

여기서 핵심 풀이는 스택에 넣기 전

넣을 수의 등장 횟수보다 더 큰 횟수를 가지는 수가 나올 때까지 pop을 해줍니다.

만약 계속 pop을해서 비어있다면 그냥 오등큰수가 없는거니 -1이 답이 되겠고

스택이 비어있지 않다면 그 수가 자신의 오등큰수가 되겠지요 그 수가 현재 수의 오큰수입니다.

 

전역 변수 설명

int N;
int arr[1000001];
int res[1000001];
stack<pair<int,int>> s; // 번호와 등장횟수
vector<int> v;

arr은 그 수의 등장 횟수를 담아줄 배열입니다.

res는 그 수의 결괏값을 담아줄 겁니다.

스택은 원소 번호와 그 원소번호의 등장 횟수를 담아줄 겁니다.

벡터에는 입력된 수를 차례대로 담아줄 것입니다.

 

아래의 코드는 main함수 설명입니다.

int main(void)
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);

	cin >> N;
	int A;
	for (int i = 0; i < N; i++)
	{
		cin >> A; // 수를 입력 받습니다.
		arr[A]++; // 그 수의 입력 횟수 배열인 arr에 A번째 구역에 +1을 해줍니다
		v.push_back(A); // 그 수를 벡터에 넣어줍니다.
	}
	solve();
	for (int i = 0; i < N; i++)
		cout << res[i] << " ";
}

 

 

	//첫 시작은 무조건 오등큰수가 없음.
	s.push(make_pair(v[N - 1], arr[v[N - 1]]));
	res[N - 1] = -1;

맨 오른쪽의 수, 즉 첫 시작의 수는 오등큰수가 존재할 수 없습니다.

 

	for(int i = v.size() - 2; i >= 0; i--) // 맨 오른쪽의 수를 제외한 맨오른쪽의 왼쪽 수 부터 0번째까지 탐색
	{
		while (!s.empty() && arr[v[i]] >= s.top().second) 
		{ // 현재 v[i]의 수보다 큰 등장 횟수가 나올때까지 pop을 해줍니다.
			s.pop();
            // 현재 v[i]의 등자 횟수보다 큰 등장횟수가 스택의 맨 위에 있거나
            // 스택이 비어버리거나 하겠죠
		}

		if (s.empty()) // 스택이 비어있다면
			res[i] = -1; // 오큰수가 없는것입니다.
		else
			res[i] = s.top().first; // 그게 아니라면 스택의 맨 위가 오큰수이겠죠
        
        //현재의 v[i]와 횟수를 스택에 넣어줍니다.
		s.push(make_pair(v[i], arr[v[i]]));
        // v[i]와 횟수를 마지막으로 스택에 넣어줍으로써
        // 문제에서 요구하는 등장횟수가 큰 수중에서 가장 왼쪽에 있는 수를 단번에 찾을 수 있습니다.
        
	}

 

문제의 핵심 문장은 아래와 같다.

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

즉, 그냥 항상 스택의 원소(요소)의 아래에는 자기보다 더 큰 등장 횟수의 수만 존재하게 만들어 줌으로써 오등큰수를 빠르게 찾을 수 있는 것이다.