백준 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 이다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, i번째 수보다 많이 등장한 수 중 가장 가까운 i+1번째 이후에 있는 수를 찾는 문제이다.

즉, 오른쪽에 있는 수중 가장 가까우면서 자신보다 많이 등장한 수를 찾으면 된다.

 

해당 문제를 푸는 방법은 stack을 이용하는 것이다.

하지만, 다른 풀이가 생각나 적용해 봤다.

 

다른 풀이는 dp를 이용하는 것이다.

dp에서는 조건에 맞는 수의 인덱스를 관리한다.

적용한 논리는 다음과 같다.

1. cnt[num[i]] < cnt[num[i+1]]
   • i+1번째 수가 i번째 수보다 많이 등장했기 때문에 dp[i] = i + 1
2. cnt[num[i]] == cnt[num[i+1]]
   • i번째 수와 i+1번째 수의 빈도수가 같기 때문에 dp[i] = dp[i+1]
3. cnt[num[i]] > cnt[num[i+1]]
   • i번째 수가 빈도수가 더 높으므로 i+1번째 수의 기록된 값을 거슬러 올라가 자신의 빈도수 보다 높은 수를 찾음

 

1번부터 살펴보면 당연한 논리이다.

i번째 수보다 빈도수가 높은 수중 가장 가까운 수는 당연히 i+1번째 수가 된다.

2번 역시 당연하다.

i번째 수와 i+1번째 수의 빈도수가 같다면 i+1번째 기록된 수가 i번째 수에서도 가장 가까운 수가 된다.

3번의 경우는 i+1번째 수가 i번째 수보다 적게 등장했다면 i+2, i+3번째 수를 살펴보며 i번째 수보다 빈도수가 높은 수를 찾아야 하지만 dp에 기록된 인덱스를 따라가면 시간을 줄일 수 있다.

int GetRoot(int idx, int cnt)
{
	if (dp[idx] == -1 || cnt < numCnt[nums[idx]]) return idx;
	return GetRoot(dp[idx], cnt);
}

 

이러한 논리를 수열의 끝에서부터 적용한다면 정답을 구할 수 있다.

그리고 한 가지 주의할 점은 빈도수를 확인하는 과정에서 map을 사용하면 시간초과가 발생한다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;
vector<int> nums;
vector<int> numCnt(1'000'001, 0);
vector<int> dp;

int GetRoot(int idx, int cnt)
{
	if (dp[idx] == -1 || cnt < numCnt[nums[idx]]) return idx;
	return GetRoot(dp[idx], cnt);
}

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

	cin >> N;
	nums.resize(N);
	dp.resize(N, -1);

	for (int i = 0; i < N; i++)
	{
		cin >> nums[i];
		numCnt[nums[i]]++;
	}

	for (int i = N - 2; i >= 0; i--)
	{
		//오른쪽 수가 현재 수보다 많이 등장했을 때
		if (numCnt[nums[i]] < numCnt[nums[i + 1]])
		{
			dp[i] = i + 1;
		}
		else if (numCnt[nums[i]] == numCnt[nums[i + 1]])
		{
			dp[i] = dp[i + 1];
		}
		else
		{
			int temp = GetRoot(i + 1, numCnt[nums[i]]);
			if (numCnt[nums[i]] < numCnt[nums[temp]]) dp[i] = temp;
		}
	}

	for (auto ans : dp)
	{
		if (ans == -1) cout << -1 << " ";
		else cout << nums[ans] << " ";
	}

	return 0;
}

 

---