C++ 문자열 변환 알고리즘: 사이클 리더 반복 기법으로 짝수 위치 요소 뒤로 옮기기

문제 정의

주어진 문자열에서 짝수 위치에 있는 모든 요소를 문자열의 끝으로 이동하는 것이 목표입니다. 이때 요소를 옮기는 과정에서 짝수 위치 요소들끼리, 그리고 홀수 위치 요소들끼리는 서로의 상대적인 순서가 유지되어야 합니다.

예를 들어, 입력 문자열이 "a1b2c3d4e5f6g7h8i9j1k2l3m4"라면, 이를 제자리(in-place)에서 O(n) 시간 복잡도로 "abcdefghijklm1234567891234" 형태로 변환해야 합니다.

알고리즘의 핵심 단계

3^k + 1 형태의 가장 큰 접두사 부분 문자열 분리: 먼저 3^k + 1이 문자열 길이 n보다 작거나 같은 최대의 음이 아닌 정수 k를 찾습니다.
사이클 리더(Cycle Leader) 반복 알고리즘 적용: 인덱스 1, 3, 9…에서 시작하여 해당 부분 문자열에 사이클 리더 반복 알고리즘을 실행합니다. 이 알고리즘은 부분 문자열 내의 모든 요소를 올바른 위치로 이동시킵니다. 즉, 알파벳은 부분 문자열의 왼쪽 절반으로, 숫자는 오른쪽 절반으로 배치됩니다.
나머지 부분에 대한 재귀적 처리: 남은 부분 문자열에 대해서도 위의 1~2단계를 재귀적으로 반복 수행합니다.
처리된 부분 문자열 병합: 이제 처리가 끝난 부분 문자열들을 하나로 연결하기만 하면 됩니다. 한쪽 끝(예: 왼쪽)에서 시작해 두 개의 부분 문자열을 골라 다음 과정을 수행합니다.
- 첫 번째 부분 문자열의 후반부를 뒤집습니다.
- 두 번째 부분 문자열의 전반부를 뒤집습니다.
- 첫 번째 부분 문자열의 후반부와 두 번째 부분 문자열의 전반부를 한꺼번에 뒤집습니다.
병합 반복: 모든 부분 문자열이 하나로 합쳐질 때까지 4번 단계를 반복합니다. 이는 첫 번째 부분 문자열이 두 번째와 병합되고, 그 결과물이 다시 세 번째와 병합되는 방식의 k-way 병합(k-way merging)과 유사한 구조입니다.

C++ 구현 코드

// 위 알고리즘의 C++ 구현
#include <bits/stdc++.h>
using namespace std;

// 두 문자를 교환(swap)하는 유틸리티 함수
void swap(char* a1, char* b1) {
    char t = *a1; *a1 = *b1; *b1 = t;
}

// str1[low1..high1] 범위의 문자열을 뒤집는 유틸리티 함수
void reverse(char* str1, int low1, int high1) {
    while (low1 < high1) {
        swap(&str1[low1], &str1[high1]);
        ++low1; --high1;
    }
}

// 짝수 위치의 모든 요소를 끝으로 이동시키는 사이클 리더 알고리즘
void cycleLeader(char* str1, int shift1, int len1) {
    int j;
    char item1;
    for (int i = 1; i < len1; i *= 3) {
        j = i;
        item1 = str1[j + shift1];
        do {
            // 홀수 인덱스인 경우
            if (j & 1)
                j = len1 / 2 + j / 2;
            // 짝수 인덱스(위치)인 경우
            else
                j /= 2;
            // 새 위치의 요소를 백업하며 교환
            swap(&str1[j + shift1], &item1);
        } while (j != i);
    }
}

// 문자열을 변환하는 메인 함수.
// 내부적으로 cycleLeader()를 호출하여 변환을 수행한다.
void moveNumberToSecondHalf(char* str1) {
    int k, lenFirst1;
    int lenRemaining1 = strlen(str1);
    int shift1 = 0;

    while (lenRemaining1) {
        k = 0;

        // 1단계: 3^k + 1 형태의 가장 큰 접두사
        // 부분 배열(subarray) 찾기
        while (pow(3, k) + 1 <= lenRemaining1)
            k++;
        lenFirst1 = pow(3, k - 1) + 1;
        lenRemaining1 -= lenFirst1;

        // 2단계: 가장 큰 부분 배열에
        // 사이클 리더 알고리즘 적용
        cycleLeader(str1, shift1, lenFirst1);

        // 4.1단계: 첫 번째 부분 배열의 후반부 뒤집기
        reverse(str1, shift1 / 2, shift1 - 1);

        // 4.2단계: 두 번째 부분 문자열의 전반부 뒤집기
        reverse(str1, shift1, shift1 + lenFirst1 / 2 - 1);

        // 4.3단계: 첫 번째 부분 문자열의 후반부와
        // 두 번째 부분 문자열의 전반부를 함께 뒤집기
        reverse(str1, shift1 / 2, shift1 + lenFirst1 / 2 - 1);

        // 첫 번째 부분 배열의 길이 늘리기
        shift1 += lenFirst1;
    }
}

// 위 함수를 테스트하는 드라이버 프로그램
int main() {
    char str1[] = "a1b2c3d4e5f6g7";
    moveNumberToSecondHalf(str1);
    cout << str1;
    return 0;
}

실행 결과

abcdefg1234567

동작 원리 요약

이 알고리즘이 효율적으로 동작하는 핵심은 두 가지입니다. 첫째, 사이클 리더 반복 알고리즘은 추가 메모리 없이 인덱스 간의 순환(cycle) 관계를 이용해 각 요소를 한 번씩만 이동시키므로, 3^k + 1 크기의 부분 배열에 대해 선형 시간 안에 재배치를 완료할 수 있습니다. 둘째, 여러 개로 나뉜 부분 문자열을 합칠 때는 배열 회전에서 자주 쓰이는 삼중 반전(triple reversal) 기법을 활용합니다. 두 구간을 각각 뒤집은 뒤 함께 다시 뒤집으면 두 블록의 위치가 서로 교환되는데, 이 덕분에 별도의 버퍼 없이도 부분 문자열들을 제자리에서 자연스럽게 이어 붙일 수 있습니다.

전체 과정에서 각 문자는 상수 번의 이동만 거치므로, 이 알고리즘은 O(n) 시간 복잡도와 O(1)의 보조 공간으로 문제의 요구 조건을 충족합니다.