C++로 구현하는 대소문자 교차 문자열 정렬 알고리즘

문자열(string)은 문자(character)들의 배열입니다. 이 문제는 문자열의 요소들을 대문자와 소문자가 번갈아 나타나도록 정렬하는 것입니다.

문제 설명 — 대소문자 교차 문자열 정렬(Alternate Lower Upper String Sort)은 대소문자가 뒤섞여 있는 정렬되지 않은 문자열이 주어졌을 때, 대문자와 소문자가 서로 교차하는 위치에 배치되면서 각각 알파벳 순으로 정렬된 상태를 유지하도록 문자열을 재배열하는 문제입니다.

구체적인 예시를 통해 문제를 더 쉽게 이해해 보겠습니다.

입력 : aFegrAfStRzsV
출력 : AaFeRfSgVrstz
설명 :
대문자 : A F R S V
소문자 : a e f g r s t z

두 그룹 모두 이미 정렬된 상태이므로, 이제 이 값들을 교차 순서로 배치하기만 하면 됩니다.

문제를 파악했으니 해결책을 설계해 보겠습니다. 가장 직관적인 방법은 대문자와 소문자를 각각 정렬된 배열로 분리한 뒤, 최종 문자열을 만들 때 두 배열의 값을 번갈아 배치하는 것입니다. 이 논리를 바탕으로 다음과 같은 알고리즘을 작성했습니다.

알고리즘

1단계 : lowercount[] 배열에 모든 소문자를 정렬된 순서로 저장합니다.
2단계 : uppercount[] 배열에 모든 대문자를 정렬된 순서로 저장합니다.
3단계 : 두 배열의 값을 번갈아 사용하여 최종 문자열을 생성합니다.
4단계 : 결과 문자열을 출력합니다.

C++ 구현 예제

#include <iostream>
using namespace std;
#define MAX 26
void alternateULSort(string& s);
int main(){
    string str = "aFegrAfStRzsV";
    cout<<"The unsorted string is : "<<str;
    cout<<"\nThe alternate lower upper sorted string is ";
    alternateULSort(str);
    cout << str << "\n";
}
void alternateULSort(string& s){
    int n = s.length();
    int lowerCount[MAX] = { 0 }, upperCount[MAX] = { 0 };
    for (int i = 0; i < n; i++) {
        if (isupper(s[i]))
            upperCount[s[i] - 'A']++;
        else
            lowerCount[s[i] - 'a']++;
    }
    int i = 0, j = 0, k = 0;
    while (k < n) {
        while (i < MAX && upperCount[i] == 0)
            i++;
        if (i < MAX) {
            s[k++] = 'A' + i;
            upperCount[i]--;
        }
        while (j < MAX && lowerCount[j] == 0)
            j++;
        if (j < MAX) {
            s[k++] = 'a' + j;
            lowerCount[j]--;
        }
    }
}

실행 결과

The unsorted string is : aFegrAfStRzsV
The alternate lower upper sorted string is AaFeRfSgVrstz

코드 동작 원리

먼저 isupper() 함수로 각 문자가 대문자인지 판별한 뒤, 'A' 또는 'a'를 기준으로 한 인덱스 위치의 카운트를 증가시킵니다. 이렇게 하면 별도의 정렬 과정 없이도 알파벳 순서가 자동으로 유지됩니다. 이후 while 루프에서 upperCount와 lowerCount를 차례로 스캔하며 아직 개수가 남아 있는 문자를 하나씩 꺼내 결과 문자열에 교차 배치합니다. 한쪽 대소문자가 먼저 소진되면, 남은 문자들은 연속으로 채워집니다.

시간 및 공간 복잡도

이 알고리즘은 카운팅 정렬(counting sort) 방식에 기반합니다. 문자열을 한 번 순회하며 각 문자의 개수를 세는 데 O(n)의 시간이 걸리고, 크기 26의 두 배열을 스캔하며 결과를 조립하는 과정 역시 선형 시간 안에 처리됩니다. 따라서 전체 시간 복잡도는 O(n)이며, 고정 크기의 두 배열만 사용하므로 공간 복잡도는 O(1)입니다.