배열 A와 정수 K가 주어졌을 때, K의 배수와 배수 사이에 위치한 요소들만 정렬하는 문제를 살펴보겠습니다. 예를 들어 배열이 [2, 13, 3, 1, 21, 7, 8, 13, 12]이고 K = 2라고 가정해 봅시다. 이 경우 출력 결과는 [2, 1, 3, 7, 13, 21, 8, 13, 12]가 됩니다.
여기서 2의 배수는 2, 8, 12입니다. 2와 8 사이에 있는 요소들은 13, 3, 1, 21, 7이며, 이들은 오름차순으로 1, 3, 7, 13, 21로 정렬됩니다. 반면 8과 12 사이에는 13 하나만 존재하므로 이미 정렬된 상태라 별도의 처리가 필요하지 않습니다. 즉, K의 배수에 해당하는 값 자체는 그대로 두고, 배수와 배수 사이에 끼어 있는 값들만 정렬 대상이 되는 것입니다.
해결 접근 방법
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- 배열을 처음부터 끝까지 순회하면서 각 요소가 K의 배수인지 확인합니다. (arr[i] % k == 0)
- K의 배수를 발견하면 해당 인덱스를 기록해 둡니다.
- 두 번째 배수를 만나는 시점부터, 현재 배수의 위치와 이전 배수의 위치 사이에 있는 모든 요소를 정렬합니다.
이 방식은 C++ STL에서 제공하는 sort() 함수를 활용하면 매우 간단하게 구현할 수 있습니다. sort() 함수는 정렬할 범위의 시작 반복자와 끝 반복자를 인자로 받으므로, 이전 배수 인덱스 바로 다음 위치부터 현재 배수 인덱스 직전까지의 범위를 지정해 주면 됩니다.
C++ 구현 예제
#include <iostream>
#include <algorithm>
using namespace std;
void display(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
void sortBetweenMultipleOfK(int arr[], int n, int k) {
int prev_index = -1;
for (int i = 0; i < n; i++) {
if (arr[i] % k == 0) {
// 첫 번째 배수가 아닌 경우에만 정렬 수행
if (prev_index != -1)
sort(arr + prev_index + 1, arr + i);
prev_index = i;
}
}
}
int main() {
int arr[] = {2, 13, 3, 1, 21, 7, 8, 13, 12};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout << "Before Sort: "; display(arr, n);
sortBetweenMultipleOfK(arr, n, k);
cout << "\nAfter Sort : "; display(arr, n);
}실행 결과
Before Sort: 2 13 3 1 21 7 8 13 12 After Sort : 2 1 3 7 13 21 8 13 12
복잡도 분석
- 시간 복잡도: 배열 전체를 한 번 순회하는 데 O(n), 각 구간의 정렬에 O(m log m)(m은 구간 길이)이 소요되므로 전체적으로 O(n log n) 수준입니다.
- 공간 복잡도: 추가적인 배열 없이 제자리(in-place) 정렬을 수행하므로 O(1)입니다.
이처럼 K의 배수 위치만 추적하면서 구간별로 정렬 범위를 지정해 주면, 배수 값 자체는 원래 자리에 그대로 유지한 채 나머지 요소들만 효율적으로 정렬할 수 있습니다.