C/C++로 모음과 자음이 번갈아 나오는 문자열 만들기

문제 개요

주어진 문자열의 문자들을 재배치하여 모음과 자음이 번갈아 위치하도록 만드는 것이 이번 문제의 목표입니다. 만약 그런 방식으로 재배치하는 것이 불가능하다면 "not possible"을 출력해야 합니다.

단, 재배치 과정에서 모음들끼리의 상대적인 순서와 자음들끼리의 상대적인 순서는 반드시 유지되어야 한다는 점이 중요합니다.

입력: abce
출력: abec

풀이 접근 방법

문자열에 포함된 모음과 자음의 개수를 각각 셉니다.
모음 개수와 자음 개수의 차이가 1보다 크면 교대 배치가 불가능하므로 "Not Possible"을 반환합니다.
모음이 자음보다 많은 경우에는 첫 번째 모음을 먼저 출력하고, 나머지 문자열에 대해 재귀적으로 같은 과정을 수행합니다.
자음이 모음보다 많은 경우에는 첫 번째 자음을 먼저 출력하고, 나머지 문자열에 대해 재귀적으로 같은 과정을 수행합니다.
모음과 자음의 개수가 같다면 첫 번째 모음과 첫 번째 자음을 비교하여 사전순으로 더 작은 문자를 먼저 출력합니다.

C++ 구현 예제

#include <iostream>
using namespace std;

bool isVowel(char ch) {
    if (ch == 'a' || ch == 'e' || ch == 'i' ||
        ch == 'o' || ch == 'u')
        return true;
    return false;
}

string createAltStr(string str1, string str2, int start, int l) {
    string finalStr = "";
    for (int i = 0, j = start; j < l; i++, j++)
        finalStr = (finalStr + str1.at(i)) + str2.at(j);
    return finalStr;
}

string findAltStr(string str) {
    int nv = 0, nc = 0;
    string vstr = "", cstr = "";
    int l = str.size();
    for (int i = 0; i < l; i++) {
        char ch = str.at(i);
        if (isVowel(ch)) {
            nv++;
            vstr = vstr + ch;
        } else {
            nc++;
            cstr = cstr + ch;
        }
    }
    if (abs(nv - nc) >= 2)
        return "no such string";
    if (nv > nc)
        return (vstr.at(0) + createAltStr(cstr, vstr, 1, nv));
    if (nc > nv)
        return (cstr.at(0) + createAltStr(vstr, cstr, 1, nc));
    if (cstr.at(0) < vstr.at(0))
        return createAltStr(cstr, vstr, 0, nv);
    return createAltStr(vstr, cstr, 0, nc);
}

int main() {
    string str = "abde";
    cout << findAltStr(str);
    return 0;
}

코드 설명

isVowel(): 전달받은 문자가 a, e, i, o, u 중 하나인지 검사하여 해당 문자가 모음인지 판별합니다.
createAltStr(): 두 개의 문자열을 인자로 받아, 지정된 시작 인덱스(start)부터 두 문자열의 문자를 하나씩 번갈아 이어 붙여 새로운 문자열을 생성합니다.
findAltStr(): 입력 문자열을 한 번 순회하면서 모음과 자음을 각각 분리하고 개수를 센 뒤, 앞서 설명한 규칙에 따라 최종 결과 문자열을 만들어 반환합니다.

실행 결과 살펴보기

예제에서 사용한 입력 문자열 "abde"의 경우, 모음은 a, e로 2개이고 자음은 b, d로 2개이므로 개수가 같습니다. 이때 첫 번째 자음 'b'보다 첫 번째 모음 'a'가 더 작으므로 모음부터 시작해 교대로 배치되며, 최종적으로 "abed"가 출력됩니다.

이 알고리즘은 문자열을 한 번만 순회하면서 모음과 자음을 분리하므로 시간 복잡도는 O(N)이며, N은 문자열의 길이입니다. 추가 공간은 모음 문자열과 자음 문자열을 저장하기 위해 필요하지만, 전체적으로 매우 효율적인 방식이라고 할 수 있습니다.