문제 개요
주어진 문자열의 문자들을 재배열하여 모음과 자음이 번갈아 위치하도록 만드는 것이 이번 문제의 목표입니다. 단, 다음 조건을 반드시 지켜야 합니다.
- 모음끼리의 상대적인 순서와 자음끼리의 상대적인 순서는 원래 문자열에서의 순서 그대로 유지해야 합니다.
- 조건에 맞게 재배열하는 것이 불가능한 경우에는 "no such string"을 출력합니다.
- 가능한 결과가 여러 개라면 그중 사전순으로 가장 작은 문자열을 출력합니다.
예시
입력 : Tutorial
출력 : Tutorila
입력 : onse
출력 : nose
두 번째 예시에서는 "nose"와 "ones"라는 두 가지 결과를 만들 수 있습니다. 이 중 "nose"가 사전순으로 더 작으므로 "nose"를 출력하게 됩니다.
알고리즘 접근 방법
- 주어진 문자열에서 모음과 자음의 개수를 각각 셉니다.
- 두 개수의 차이가 1보다 크다면 교대 배치가 불가능하므로 "Not Possible"을 반환합니다.
- 모음이 자음보다 많다면 첫 번째 모음으로 시작하고, 나머지 문자열에 대해 같은 과정을 반복합니다.
- 자음이 모음보다 많다면 첫 번째 자음으로 시작하고, 나머지 문자열에 대해 반복합니다.
- 두 개수가 같다면 첫 번째 모음과 첫 번째 자음을 비교하여 더 작은 문자를 앞에 배치합니다.
C++ 구현
// 모음과 자음이 번갈아 나오는 문자열의 C++ 구현
#include <bits/stdc++.h>
using namespace std;
// 'ch1'이 모음인지 판별하는 함수
bool isVowel(char ch1){
if (ch1 == 'a' || ch1 == 'e' || ch1 == 'i' ||
ch1 == 'o' || ch1 =='u')
return true;
return false;
}
// 모음/자음 문자열을 받아 교대로 배치된 문자열 생성
// str1[0...l2-1]과 str2[start...l3-1] 사용
string createAltStr(string str1, string str2,
int start1, int l1){
string finalStr1 = "";
// 모음/자음 문자를 먼저 추가한 뒤
// 자음/모음 문자를 이어서 추가
for (int i=0, j=start1; j<l1; i++, j++)
finalStr1 = (finalStr1 + str1.at(i)) + str2.at(j);
return finalStr1;
}
// 원하는 교대 모음·자음 문자열을 찾는 함수
string findAltStr(string str3){
int nv1 = 0, nc1 = 0;
string vstr1 = "", cstr1 = "";
int l1 = str3.size();
for (int i=0; i<l1; i++){
char ch1 = str3.at(i);
// 모음 개수를 세고 모음 문자열 갱신
if (isVowel(ch1)){
nv1++;
vstr1 = vstr1 + ch1;
}
// 자음 개수를 세고 자음 문자열 갱신
else{
nc1++;
cstr1 = cstr1 + ch1;
}
}
// 만들 수 있는 문자열이 없는 경우
if (abs(nv1-nc1) >= 2)
return "no such string";
// 모음 문자열의 첫 문자를 제외한 뒤
// cstr1[0...nc1-1]과 vstr1[1...nv1-1]로 교대 문자열 생성
if (nv1 > nc1)
return (vstr1.at(0) + createAltStr(cstr1, vstr1, 1, nv1));
// 자음 문자열의 첫 문자를 제외한 뒤
// vstr1[0...nv1-1]과 cstr1[1...nc1-1]로 교대 문자열 생성
if (nc1 > nv1)
return (cstr1.at(0) + createAltStr(vstr1, cstr1, 1, nc1));
// 모음 문자열과 자음 문자열의
// 길이가 같은 경우
// 자음으로 시작하는 문자열 생성
if (cstr1.at(0) < vstr1.at(0))
return createAltStr(cstr1, vstr1, 0, nv1);
// 모음으로 시작하는 문자열 생성
return createAltStr(vstr1, cstr1, 0, nc1);
}
// 위 함수를 테스트하는 드라이버 프로그램
int main(){
string str3 = "Tutorial";
cout<< findAltStr(str3);
return 0;
}
실행 결과
Tutorila
동작 방식 설명
이 코드는 먼저 입력 문자열을 한 번 순회하면서 모음만 모은 문자열(vstr1)과 자음만 모은 문자열(cstr1)을 각각 만듭니다. 이때 원래 문자열에서의 등장 순서가 그대로 보존됩니다.
이후 두 문자열의 길이를 비교하여 어느 쪽으로 시작할지 결정하고, createAltStr 함수가 두 문자열에서 번갈아 한 글자씩 가져와 최종 결과를 조립합니다. 개수가 같은 경우에는 첫 글자끼리 비교하여 사전순으로 더 작은 문자로 시작하는 쪽을 선택함으로써, 항상 사전순으로 가장 작은 답을 얻을 수 있습니다.
시간 복잡도
시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이를 의미하며, 문자열을 한 번만 순회하면 되기 때문에 매우 효율적입니다.