C++ 연결 리스트에서 모음과 자음 노드 재배열하기

이 기법에서는 연결 리스트를 순회하면서 키 값이 모음인 노드는 앞쪽으로, 자음인 노드는 뒤쪽으로 이동시킵니다. 중요한 점은 이동 과정에서 각 노드들의 원래 상대적 순서가 그대로 유지된다는 것입니다(안정 정렬 방식).

동작 예시

입력: A-M-A-Z-O-N
출력: A-A-O-M-Z-N
시간 복잡도: O(N), 공간 복잡도: O(1)

위 예시에서 A, A, O는 모음이므로 앞쪽으로 이동하고, M, Z, N은 자음이므로 뒤쪽으로 이동합니다. 각 그룹 내부에서는 입력 순서가 유지되는 것을 확인할 수 있습니다.

알고리즘 설명

구현 방식은 다음과 같습니다.

1. 모음용과 자음용으로 각각 더미(dummy) 헤드 노드를 생성합니다.
2. 원본 리스트를 처음부터 끝까지 순회하면서 각 노드를 분리합니다.
3. isVowel() 함수로 해당 문자가 모음인지 판별합니다.
4. 모음이면 모음 리스트의 끝에, 자음이면 자음 리스트의 끝에 노드를 삽입합니다.
5. 순회가 끝나면 모음 리스트의 마지막 노드를 자음 리스트의 첫 번째 실제 노드와 연결하고, 더미 노드를 제거한 뒤 결과 리스트를 반환합니다.

노드를 새로 생성하지 않고 기존 노드의 포인터만 재연결하므로 추가 메모리 사용 없이 O(1) 공간 복잡도를 달성할 수 있습니다.

예제 코드

#include<iostream>
using namespace std;

class Node1{
    public:
    char var1;
    Node1 *next1;
    Node1(char v,Node1 *next1=NULL):var1(v),next1(next1){}
};

// 배열로부터 연결 리스트 생성
Node1 *make_list(char array1[],int size1){
    if(size1 ==0)
    return NULL;
    else {
        Node1 *head = new Node1('o');
        Node1 *temp = head;
        for(int i=0;i<size1;++i) {
            temp->next1 = new Node1(array1[i]);
            temp=temp->next1;
        }
        temp=head;
        head = head->next1;
        delete temp;
        return head;
    }
}

// 리스트 출력
void print_list(Node1 *head){
    while(head){
        cout<<head->var1<<"--";
        head = head->next1;
    }
    cout<<"END"<<endl;
}

// 특정 노드 뒤에 새 노드 삽입
void insertAfter(Node1** temp,Node1 *n){
    n->next1 = (*temp)->next1;
    (*temp)->next1 = n;
}

// 모음 여부 판별
bool isVowel(char v){
    switch(v){
        case 'A':
        case 'E':
        case 'I':
        case 'O':
        case 'U':
        return true;
        default:
        return false;
    }
}

// 모음과 자음 그룹별로 재배열
Node1 *groupByVowels(Node1 *head){
    Node1 *vowel=NULL,*consonant=NULL;
    vowel = new Node1('L');   // 모음용 더미 헤드
    consonant = new Node1('C'); // 자음용 더미 헤드
    Node1 *tv = vowel,*tc=consonant;
    for(Node1 *temp=head;temp;){
        Node1 *tt = temp->next1;
        if(isVowel(temp->var1)){
            insertAfter(&tv,temp);
            tv = tv->next1;
        }
        else {
            insertAfter(&tc,temp);
            tc=tc->next1;
        }
    temp = tt;
    }
    // 모음 리스트 뒤에 자음 리스트 연결
    tv->next1 = consonant->next1;
    tv = vowel;
    vowel=vowel->next1;
    delete tv;
    return vowel;
}

int main(){
    char array1[] = {'A','M','A','Z','O','N'};
    Node1 *head = make_list(array1,sizeof(array1)/sizeof(array1[0]));
    print_list(head);
    head = groupByVowels(head);
    print_list(head);
}

실행 결과

A--M--A--Z--O--N--END
A--A--O--M--Z--N--END

첫 번째 줄은 원본 리스트이고, 두 번째 줄은 모음(A, A, O)이 앞쪽으로, 자음(M, Z, N)이 뒤쪽으로 재배열된 결과입니다. 전체 리스트를 한 번만 순회하므로 시간 복잡도는 O(N)이며, 새로운 노드를 만들지 않고 포인터만 조작하므로 공간 복잡도는 O(1)입니다.