문제 설명
N개의 정수로 이루어진 배열이 주어집니다. 배열 요소를 재배치하여 다음 요소가 이전 요소보다 크도록, 즉 arr[i+1] > arr[i] 조건을 만족하는 인접 쌍의 개수를 최대화해야 합니다.
예시
입력 배열이 {300, 400, 400, 300}이라면, 재배치된 배열은 다음과 같습니다.
{300, 400, 300, 400}
이 배치에서는 arr[i+1] > arr[i] 조건을 만족하는 인덱스가 2개입니다(400 > 300이 두 번 성립). 따라서 정답은 2입니다.
알고리즘
- 배열의 모든 요소가 서로 다르다면, 오름차순으로 정렬하기만 하면 모든 인접 쌍이 조건을 만족하므로 정답은 n-1입니다(n은 요소의 개수).
- 중복된 요소가 존재한다면, 정답은 n - 최대 빈도수(maxFrequency)입니다. 가장 많이 등장하는 값이 f번 나타나면, 같은 값이 다시 등장할 때마다 그 사이에 반드시 조건을 만족하지 못하는 구간이 하나 이상 생기므로 최소 f-1개의 인접 쌍은 조건을 충족할 수 없습니다.
구현 예제
다음은 위 알고리즘을 C++로 구현한 코드입니다. 이 구현은 배열의 각 값이 MAX(1000)보다 작다는 전제 아래, 도수 계산 방식으로 최대 빈도수를 구한 뒤 n에서 뺀 값을 반환합니다.
#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
복잡도 분석
시간 복잡도: O(n) — 배열을 두 번 순회합니다.
공간 복잡도: O(MAX) — 각 값의 빈도수를 저장하는 보조 배열이 필요합니다.