[BOJ][C++] 백준 17299번 오등큰수
Updated:
17299번 오등큰수
1. 문제 정보
백준 온라인 저지 [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 이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, …, AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
출력
총 N개의 수 NGF(1), NGF(2), …, NGF(N)을 공백으로 구분해 출력한다.
예제 입력1
7
1 1 2 3 4 2 1
예제 출력1
-1 -1 1 2 2 1 -1
시간 / 메모리 제한
1초 / 128MB
2. 생각
- 문제 17298번 오등큰수와 비슷한 문제였습니다. 문제 17298번과 다른 점은 다음과 같습니다. 문제 17298번은 i번째 수보다 큰 오른쪽에 있는 수를 찾는 문제이고, 문제 17299번은 i번째 수보다 등장 빈도수가 많은 오른쪽에 있는 수를 찾는 문제입니다.
-
따라서 빈도수를 구하기 위해서는 각 수가 몇 번 등장했는지 체크할 배열 cnt가 필요합니다. 배열을 입력받을 때 그 배열 값에 해당하는 수가 몇 번 등장했는지 cnt 배열 인덱스에 맞춰 체크합니다.
- 따라서 비교하는 것도 빈도수를 나타내는 cnt 배열을 통해 비교합니다.이 문제에서는 스택 맨 위에 있는 값의 빈도수 cnt[arr[st.top]]]과 i번째 입력 값의 빈도수 cnt[arr[i]]와 비교해야합니다. (문제 17298번 오큰수는 스택 맨 위에 있는 값 arr[st.top]]과 i번째 입력 값arr[i]와 비교했습니다. )
3. 소스코드 (C++)
