정수형 배열 'int arr[]'와 정수형 변수 'x'가 주어졌을 때, 배열의 모든 요소 중 주어진 정수 'x'로 나누어 떨어지는 요소들만 찾아 오름차순으로 재배열하는 것이 이번 문제의 목표입니다. 이때 x의 배수가 아닌 요소들은 원래 자리에 그대로 유지되며, 배수인 요소들은 서로 상대적인 위치 관계를 지키면서 정렬된 값으로 교체됩니다.
입출력 시나리오 살펴보기
입력 − int arr[] = {4, 24, 3, 5, 7, 22, 12, 10}, int x = 2
출력 − x = 2의 배수인 요소들을 오름차순으로 재배열한 결과: 4 10 3 5 7 12 22 24
설명 − 값이 {4, 24, 3, 5, 7, 22, 12, 10}인 정수형 배열과 값이 2인 x가 주어집니다. 먼저 배열에서 2로 나누어 떨어지는 요소, 즉 4, 24, 22, 12, 10을 찾아냅니다. 이 요소들을 오름차순으로 정렬하면 4, 10, 12, 22, 24가 되고, 이를 원래 배수가 있던 위치에 순서대로 채워 넣으면 최종 출력은 4 10 3 5 7 12 22 24가 됩니다.
입력 − int arr[] = {4, 24, 3, 5, 7, 22, 12, 10}, int x = 3
출력 − x = 3의 배수인 요소들을 오름차순으로 재배열한 결과: 4 3 12 5 7 22 24 10
설명 − 같은 배열에서 x의 값이 3으로 주어진 경우입니다. 배열에서 3으로 나누어 떨어지는 요소는 3, 24, 12입니다. 이들을 오름차순으로 정렬하면 3, 12, 24가 되고, 원래 배수가 있던 위치(인덱스 1, 2, 6)에 순서대로 배치하면 최종 출력은 4 3 12 5 7 22 24 10이 됩니다.
프로그램에 사용된 접근 방식
정수형 배열을 선언하고, sizeof 연산자로 배열의 크기를 계산하여 size 변수에 저장합니다. 재배열의 기준이 되는 정수형 변수 'x'도 함께 선언합니다.
배열 데이터를 Rearrange_Elements(arr, size, x) 함수에 전달합니다.
Rearrange_Elements(arr, size, x) 함수 내부에서 다음 과정을 수행합니다.
정수형 값을 저장할 vector 타입 변수 vec을 생성합니다.
i를 0부터 size 미만까지 반복하는 FOR 루프를 실행합니다. 루프 안에서 arr[i] % x == 0 조건을 만족하면 해당 값을 vec에 추가(push_back)합니다.
C++ STL의 sort 메서드를 사용해 vec을 오름차순으로 정렬합니다. 이때 begin()과 end()를 매개변수로 전달합니다.
다시 i를 0부터 size 미만까지 반복하면서 arr[i] % x == 0 조건을 만족하는 위치에 정렬된 값을 vec[j++] 형태로 순서대로 대입합니다.
for 루프로 배열의 첫 번째 요소부터 마지막 요소까지 순회하며 결과를 출력합니다.
예제
#include <bits/stdc++.h>
using namespace std;
void Rearrange_Elements(int arr[], int size, int x){
vector<int> vec;
int j = 0;
for(int i = 0; i < size; i++){
if(arr[i] % x == 0){
vec.push_back(arr[i]);
}
}
sort(vec.begin(), vec.end());
for (int i = 0; i < size; i++){
if(arr[i] % x == 0){
arr[i] = vec[j++];
}
}
cout<<"Rearrangement of all elements of array which are multiples of x "<<x<<" in increasing order is: ";
for(int i = 0; i < size; i++){
cout << arr[i] << " ";
}
}
int main(){
int arr[] = {4,24, 3, 5, 7, 22, 12, 10};
int x = 2;
int size = sizeof(arr) / sizeof(arr[0]);
Rearrange_Elements(arr, size, x);
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Rearrangement of all elements of array which are multiples of x 2 in increasing order is: 4 10 3 5 7 12 22 24
이 알고리즘의 시간 복잡도는 O(n log n)입니다. 배열을 두 번 순회하는 O(n) 연산과 배수 요소들을 정렬하는 O(k log k)(k는 배수의 개수) 연산이 결합되기 때문입니다. 공간 복잡도는 배수 요소를 저장하는 벡터로 인해 O(k)입니다.