문제 설명
N개의 정수 배열이 주어지면 다음 배열 요소가 이전 요소보다 크도록 배열 요소를 재배열합니다. arr[i+1]> arr[i]
예시
입력 배열이 {300, 400, 400, 300}이면 재배열된 배열은 -
{300, 400, 300, 400}. 이 솔루션에서 조건 arr[i+1]> arr[i]인 2개의 인덱스를 얻습니다. 따라서 답은 2입니다.
알고리즘
- 모든 요소가 고유한 경우 대답은 단순히 n-1입니다. 여기서 n은 배열의 요소 수입니다.
- 반복되는 요소가 있는 경우 답은 n – maxFrequency입니다.
예시
이제 예를 살펴보겠습니다 -
#include <bits/stdc++.h>
#define MAX 1000
using namespace std;
int getMaxIndices(int *arr, int n) {
int count[MAX] = {0};
for (int i = 0; i < n; ++i) {
count[arr[i]]++;
}
int maxFrequency = 0;
for (int i = 0; i < n; ++i) {
if (count[arr[i]] > maxFrequency) {
maxFrequency = count[arr[i]];
}
}
return n - maxFrequency;
}
int main() {
int arr[] = {300, 400, 300, 400}; int n = sizeof(arr) / sizeof(arr[0]);
cout << "Answer = " << getMaxIndices(arr, n) << endl;
return 0;
} 출력
Answer = 2