C++ 배열 재배치 알고리즘: 짝수 인덱스에는 짝수를, 홀수 인덱스에는 홀수를

이 문제에서는 n/2개의 짝수와 n/2개의 홀수로 구성된 크기 n의 배열 arr[]가 주어집니다. 우리의 목표는 짝수는 짝수 인덱스(0, 2, 4...)에, 홀수는 홀수 인덱스(1, 3, 5...)에 위치하도록 배열을 재배치하는 프로그램을 작성하는 것입니다.

예제로 문제 이해하기

입력: arr[] = {5, 1, 6, 4, 3, 8}

출력: arr[] = {6, 1, 5, 4, 3, 8}

참고로 조건을 만족하는 결과 배열은 위 예시 외에도 여러 가지가 존재할 수 있습니다. 핵심은 모든 짝수가 짝수 인덱스에, 모든 홀수가 홀수 인덱스에 자리한다는 점입니다.

해결 접근 방식

가장 직관적인 방법은 배열 전체를 순회하면서 올바르지 않은 위치에 놓인 요소를 찾아, 역시 부적절한 위치에 있는 다음 값과 교환하는 것입니다. 하지만 짝수 전용 인덱스(eIndex)와 홀수 전용 인덱스(oIndex)라는 두 개의 포인터를 활용하면 훨씬 효율적으로 처리할 수 있습니다.

동작 원리는 다음과 같습니다.

• eIndex를 2씩 증가시키며 짝수 인덱스에서 짝수가 아닌 값을 찾습니다.
• oIndex를 2씩 증가시키며 홀수 인덱스에서 홀수가 아닌 값을 찾습니다.
• 두 값이 모두 발견되면 서로 교환(swap)하고, 배열의 끝에 도달할 때까지 이 과정을 반복합니다.

이 알고리즘은 각 요소를 한 번씩만 방문하므로 시간 복잡도는 O(n)이며, 추가 배열 없이 제자리(in-place)에서 수행되기 때문에 공간 복잡도는 O(1)입니다.

솔루션 구현 예제

#include <iostream>
using namespace std;

void O_EReshuffle(int arr[], int n) {

    int oIndex = 1;
    int eIndex = 0;

    for(int i = 0; i < n; ) {

        while (eIndex < n && arr[eIndex] % 2 == 0)
            eIndex += 2;

        while (oIndex < n && arr[oIndex] % 2 == 1)
            oIndex += 2;

        if (eIndex < n && oIndex < n)
            swap (arr[eIndex], arr[oIndex]);

        else
            break;
    }
}

int main()
{
    int arr[] = { 5, 1, 6, 4, 3, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "재배열 전 배열: ";
    for(int i = 0; i < n ; i++){
        cout<<arr[i]<<"\t";
    }
    O_EReshuffle(arr, n);

    cout<<"\n재배열 후 배열: ";
    for(int i = 0; i < n ; i++){
        cout<<arr[i]<<"\t";
    };

    return 0;
}

실행 결과

재배열 전 배열: 5	1	6	4	3	8
재배열 후 배열: 4	1	6	5	8	3