양수와 음수가 함께 포함된 임의의 크기를 가진 정수형 배열 arr[]가 주어집니다. 이때 배열을 재배열하여 모든 짝수 위치(인덱스)의 요소가 홀수 위치(인덱스)의 요소보다 작아지도록 만들고, 그 결과를 출력하는 것이 목표입니다.
입출력 시나리오 살펴보기
입력 − int arr[] = {2, 1, 4, 3, 6, 5, 8, 7}
출력 −
정렬 전 배열: 2 1 4 3 6 5 8 7
짝수 인덱스 요소는 더 작고 홀수 인덱스 요소는 더 크도록 재배열한 결과: 1 4 2 6 3 8 5 7
설명 − 크기가 8인 정수 배열이 주어졌습니다. 짝수 위치의 모든 요소가 홀수 위치의 요소보다 작도록 배열을 재배열하면, 연산 후 완성되는 배열은 1 4 2 6 3 8 5 7입니다.
입력 − int arr[] = {10, -1, 7, -5, 6, -9}
출력 −
정렬 전 배열: 10 -1 7 -5 6 -9
재배열한 결과: -1 10 -5 7 -9 6
설명 − 크기가 6이며 양수와 음수를 모두 포함하는 정수 배열이 주어졌습니다. 짝수 위치의 요소가 항상 홀수 위치의 요소보다 작도록 재배열하면, 최종적으로 만들어지는 배열은 -1 10 -5 7 -9 6입니다.
프로그램에서 사용하는 접근 방식
- 정수형 요소로 이루어진 배열을 입력받고, 배열의 크기를 계산합니다.
- FOR 루프를 사용하여 재배열 작업을 수행하기 전의 원본 배열을 출력합니다.
- 배열과 배열의 크기를 매개변수로 전달하며 Rearrangement(arr, size) 함수를 호출합니다.
- Rearrangement(arr, size) 함수 내부에서 다음 작업을 수행합니다.
- i를 0부터 size-1 미만까지 반복하는 FOR 루프를 시작합니다. 루프 안에서 i % 2 == 0(짝수 인덱스)이라면 arr[i] > arr[i + 1]인지 검사하고, 조건이 참이면 C++ STL의 swap 메서드에 arr[i]와 arr[i + 1]을 전달하여 두 값을 교환합니다.
- i % 2 != 0(홀수 인덱스)이라면 arr[i] < arr[i + 1]인지 검사하고, 조건이 참이면 마찬가지로 STL의 swap 메서드를 호출해 두 값을 교환합니다.
- 재배열이 완료된 배열을 출력합니다.
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가적인 메모리 없이 제자리(in-place)에서 교환을 수행하므로 공간 복잡도는 O(1)입니다.
예제
#include <iostream>
using namespace std;
void Rearrangement(int* arr, int size){
for(int i = 0; i < size - 1; i++){
if(i % 2 == 0){
if(arr[i] > arr[i + 1]){
swap(arr[i], arr[i + 1]);
}
}
if(i % 2 != 0){
if(arr[i] < arr[i + 1]){
swap(arr[i], arr[i + 1]);
}
}
}
}
int main(){
//배열 입력
int arr[] = {2, 1, 4, 3, 6, 5, 8, 7};
int size = sizeof(arr) / sizeof(arr[0]);
//원본 배열 출력
cout<<"Array before Arrangement: ";
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
//배열 재정렬 함수 호출
Rearrangement(arr, size);
//재정렬 후 배열 출력
cout<<"\nRearrangement of an array such that even index elements are smaller and odd index elements are greater is: ";
for(int i = 0; i < size; i++){
cout<< arr[i] << " ";
}
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 생성됩니다.
Array before Arrangement: 2 1 4 3 6 5 8 7 Rearrangement of an array such that even index elements are smaller and odd index elements are greater is: 1 4 2 6 3 8 5 7