Problem : 오등큰수

유형 : 스택

문제 설명

크기가 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 이다.

예제 입력

7
1 1 2 3 4 2 1

예제 출력

1	`-1 -1 1 2 2 1 -1`

해결 전략

먼저 해당 숫자가 몇 번이나 등장했는지 관리한다.
그리고 다시 처음부터 순열을 탐색한다

새로운 숫자의 등장 빈도가, 스택 top에 있는 숫자의 등장 빈도 보다 크다면
따로 관리하고 있는 배열 answer에 NGF를 저장하고, 스택에서 제거한다.
스택에는 더 많이 등장한 숫자를 만나지 못한 수들의 집합이 유지된다.

방금 들어온 수는 우측에 아무런 숫자가 없으므로 항상 스택에 들어간다.

주의할 점

먼저 모든 숫자의 빈도수를 계산해야 한다.
순차적으로 스택을 쌓아가며 빈도수를 계산하면 안된다.
1 1 2 3 4 2 1 에서 두번째 1과 세번째 2을 비교할때
1의 빈도수는 2 가 아니라 3 이다.

풀이

수열을 한번 순회하며 숫자들의 빈도수를 체크한다.

다시 수열을 처음부터 순회하며 답을 answer 배열에 기록한다.

스택 top 숫자의 빈도수가, 새로운 숫자의 빈도수보다 작다면, NFG(스택맨위 숫자) = 새로운 숫자 가 된다.
- 그리고 해당 숫자는 스택에서 제거한다.
- 왜냐하면 큰 수 중에서 가장 왼쪽에 있는 수를 찾았기 때문이다.
- 이후에 더 큰 수가 나와도, 의미가 없다.
아니라면 스택에 해당 숫자를 넣어둔다.

코드

#include <bits/stdc++.h>

#define pp pair<int, int>
#define MAX 1000001
#define index first
#define value second

using namespace std;

int n;
int arr[MAX], answer[MAX];
int visit[MAX];

stack<pp> s;

void output() {
	for (int i = 0; i < n; ++i) {
		cout << answer[i] << " ";
	}
}

void solve() {
	int num;
	for (int i = 0; i < n; ++i) {
		num = arr[i];
		while (!s.empty()) {
			auto cur = s.top();
			if (visit[cur.value] >= visit[num]) break;
			answer[cur.index] = num;
			s.pop();
		}
		s.push({ i,num });
	}
}

void input() {
	memset(answer, -1, sizeof(answer));
	cin >> n;
	int num;
	for (int i = 0; i < n; ++i) {
		cin >> num;
		visit[num]++;
		arr[i] = num;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "r", stdin);

	input();
	solve();
	output();

	return 0;
}

피드백

문제 한번에 제대로 읽기.