문제 개요
이 문제에서는 하나의 배열이 주어지며, 모든 양수는 짝수 인덱스에, 모든 음수는 홀수 인덱스에 위치하도록 배열을 변환하는 것이 목표입니다.
양수와 음수의 개수가 서로 다를 수 있는데, 이 경우 남는 값들은 원래 자리에 그대로 두면 됩니다.
예시를 통해 문제를 이해해 보겠습니다.
입력 − {3, 5, -1, 19, -7, -2}
출력 − {3, -1, 5, -7, 19, -2}
이 문제를 해결하려면 배열에서 순서가 어긋난 요소를 찾아 적절한 위치로 옮겨야 합니다. 이를 찾는 방법은 여러 가지가 있으며, 여기서는 대표적인 두 가지 방법을 살펴보겠습니다.
방법 1: 순차 탐색 후 교환
이 방법은 배열을 단순히 순회하면서 제자리에 있지 않은 요소(즉, 짝수 인덱스에 있지 않은 양수 또는 홀수 인덱스에 있지 않은 음수)를 처음 발견했을 때 이를 교환(swap)하는 방식입니다. 이 과정을 배열 전체를 순회할 때까지 반복합니다.
예제
해결 방법의 구현을 보여주는 프로그램입니다.
#include<iostream>
using namespace std;
void swapElements(int* a, int i , int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
return ;
}
void printArray(int* a, int n){
for(int i = 0; i<n; i++)
cout<<a[i]<<"\t";
cout<<endl;
return ;
}
void generateOrderedArray(int arr[], int n){
for(int i = 0; i <n; i++){
if(arr[i] >= 0 && i % 2 == 1){
for(int j = i + 1; j <n; j++){
if(arr[j] < 0 && j % 2 == 0){
swapElements(arr, i, j);
break ;
}
}
}
else if(arr[i] < 0 && i % 2 == 0){
for(int j = i + 1; j <n; j++){
if(arr[j] >= 0 && j % 2 == 1){
swapElements(arr, i, j);
break;
}
}
}
}
printArray(arr, n);
}
int main(){
int arr[] = { 1, -3, 5, 6, -3, 6, 7, -4, 9, 10 };
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"Inital Array is : ";
printArray(arr, n);
cout<<"Array with positive numbers at even index and negative numbers at odd index :";
generateOrderedArray(arr,n);
return 0;
}출력 결과
Inital Array is : 3 5 -1 19 -7 -2 Array with positive numbers at even index and negative numbers at odd index : 3 -1 5 -7 19 -2
방법 2: 투 포인터(Two Pointer) 기법
이 방법은 퀵 정렬(quick sort)의 분할 기법과 유사한 절차를 사용합니다. 두 개의 포인터를 활용하는데, 하나는 양수용이고 다른 하나는 음수용입니다. 양수 포인터는 인덱스 0(짝수 인덱스)에, 음수 포인터는 인덱스 1(홀수 인덱스)에 설정한 뒤, 각 포인터를 2칸씩 앞으로 이동시킵니다.
양수 포인터가 음수를 만나거나, 음수 포인터가 양수를 만나면 해당 지점에서 이동을 멈춥니다. 두 포인터가 모두 멈췄을 때 두 요소를 교환합니다. 어느 한 포인터라도 배열의 범위를 벗어나면 실행을 종료합니다.
예제
해결 방법의 구현을 보여주는 프로그램입니다.
#include <iostream>
using namespace std;
void swapElements(int* a, int i , int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
return ;
}
void printArray(int *a, int n){
for (int i = 0; i <n; i++)
cout<<a[i]<<"\t";
cout<<endl;
}
void generateOrderedArray(int a[], int size){
int positive = 0, negative = 1;
while (1) {
while (positive < size && a[positive] >= 0)
positive += 2;
while (negative <size && a[negative] <= 0)
negative += 2;
if (positive < size && negative < size)
swapElements(a, positive, negative);
else
break;
}
}
int main(){
int arr[] = { 3, 5, -1, 19, -7, -2 };
int n = (sizeof(arr) / sizeof(arr[0]));
cout<<"Inital Array is : ";
printArray(arr, n);
cout<<"Array with positive numbers at even index and negative numbers at odd index : ";
generateOrderedArray(arr, n);
printArray(arr, n);
return 0;
}출력 결과
Inital Array is : 3 5 -1 19 -7 -2 Array with positive numbers at even index and negative numbers at odd index : 3 -1 5 -7 19 -2