문제 개요
양수와 음수가 섞여 있는 정수형 배열 arr[]가 임의의 크기로 주어집니다. 이 배열을 다음 규칙에 따라 재배열하는 것이 과제입니다.
- 배열에서 가장 작은 원소가 홀수라면 → 홀수를 먼저, 짝수를 다음에 두는 방식으로 교대 배치합니다.
- 배열에서 가장 작은 원소가 짝수라면 → 짝수를 먼저, 홀수를 다음에 두는 방식으로 교대 배치합니다.
- 한쪽(홀수 또는 짝수) 원소의 개수가 부족하여 교대 배치를 계속할 수 없는 자리에는 0을 채워 넣고 결과를 출력합니다.
입출력 예시
입력 − int arr[] = { 1, 1, 2, 2, 5, 4 }
출력 − 오름차순으로 홀수·짝수 값을 교대로 재배열한 결과: 1 2 1 2 5 4
설명 − 정수형 배열이 주어졌습니다. 배열에서 가장 작은 원소는 1이며 이는 홀수입니다. 따라서 홀수를 먼저, 짝수를 다음에 두는 방식으로 배치하면 최종 결과는 1 2 1 2 5 4가 됩니다.
입력 − int arr[] = { 6, 3, 2, 8, 10, 4 }
출력 − 오름차순으로 홀수·짝수 값을 교대로 재배열한 결과: 2 3 4 0 6 0
설명 − 정수형 배열이 주어졌습니다. 배열에서 가장 작은 원소는 2이며 이는 짝수입니다. 따라서 짝수를 먼저, 홀수를 다음에 두는 방식으로 배치하되, 홀수 원소가 부족한 자리는 0으로 채워 최종 결과는 2 3 4 0 6 0이 됩니다.
프로그램에서 사용하는 접근 방식
- 정수형 요소로 구성된 배열을 입력받고 배열의 크기를 계산합니다.
- C++ STL의 sort 함수에 배열과 배열의 크기를 전달하여 배열을 오름차순으로 정렬합니다.
- 정수형 변수를 선언하고 Rearrangement(arr, size) 함수의 호출 결과를 저장합니다.
- Rearrangement(arr, size) 함수 내부에서는 다음을 수행합니다.
- 정수형 데이터를 저장하는 벡터 두 개(vec_1, vec_2)를 생성합니다.
- 정수형 임시 변수 temp를 선언하고 0으로 초기화합니다.
- bool형 변수 check를 선언하고 FALSE로 초기화합니다.
- i를 0부터 size 미만까지 반복하는 FOR 루프를 시작합니다. 루프 안에서 arr[i] % 2 == 0이면 arr[i]를 vec_1에 push하고, 그렇지 않으면 vec_2에 push합니다.
- 정수형 변수 i와 j를 선언하고 0으로 초기화합니다. arr[0] % 2 == 0이면 check를 true로 설정합니다.
- temp가 size보다 작은 동안 WHILE 루프를 실행합니다. 루프 안에서 check가 true이면 arr[temp++]에 vec_1[i++]를 대입하고 check를 반전하며, 그렇지 않으면 arr[temp++]에 vec_2[j++]를 대입하고 check를 반전합니다.
- 결과를 출력합니다.
참고: 아래 예제 코드는 두 그룹의 개수가 같아 교대 배치가 끝까지 가능한 경우를 전제로 작성되었습니다. 한쪽(홀수 또는 짝수) 원소가 먼저 소진되어 나머지 자리를 0으로 채워야 하는 경우에는 인덱스 경계 검사(i < vec_1.size(), j < vec_2.size())를 추가해야 안전하게 동작합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
vector<int> vec_1, vec_2;
int temp = 0;
bool check = false;
for(int i = 0; i < size; i++){
if(arr[i] % 2 == 0){
vec_1.push_back(arr[i]);
}
else{
vec_2.push_back(arr[i]);
}
}
int i = 0;
int j = 0;
if(arr[0] % 2 == 0){
check = true;
}
while(temp < size){
if(check == true){
arr[temp++] = vec_1[i++];
check = !check;
}
else{
arr[temp++] = vec_2[j++];
check = !check;
}
}
}
int main(){
int arr[] = { 1, 1, 2, 2, 5, 4 };
int size = sizeof(arr) / sizeof(int);
// 배열을 오름차순으로 정렬
sort(arr, arr + size);
cout<<"오름차순으로 홀수·짝수 값을 교대로 재배열한 결과: ";
Rearrangement(arr, size);
for(int i = 0; i < size; i++){
cout << arr[i] << " ";
}
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
오름차순으로 홀수·짝수 값을 교대로 재배열한 결과: 1 2 1 2 5 4