이 문제에서는 하나의 문자열이 주어지며, 이 문자열에서 조건을 만족하는 모든 부분 시퀀스(subsequence)를 찾아야 합니다. 찾으려는 부분 시퀀스는 모음(vowel)으로 시작해서 자음(consonant)으로 끝나야 합니다.
문자열(string)은 여러 개의 문자가 일렬로 나열된 배열을 의미합니다.
이 문제에서 생성해야 할 부분 시퀀스는 원본 문자열에서 일부 문자를 삭제하는 방식으로 만들 수 있으며, 삭제 후에도 남은 문자들의 순서는 절대 변경되지 않습니다.
입력: 'abc' 출력: ab, ac, abc
이 문제를 해결하려면 문자열을 차례대로 탐색하면서 모음 위치를 하나 고정한 뒤, 그 뒤에 올 수 있는 자음들을 확인하면 됩니다. 문제 풀이 과정을 알고리즘으로 정리하면 다음과 같습니다.
알고리즘
- 변수 i를 사용해 문자열의 각 문자를 처음부터 끝까지 반복합니다.
- i번째 문자가 모음인지 검사합니다.
- j번째 문자가 자음인지 검사합니다.
- i번째 문자부터 j번째 문자까지 잘라낸 부분 문자열을 집합(set)에 추가합니다.
- 위 과정을 재귀적으로 반복하여 문자열에서 만들 수 있는 모든 부분 시퀀스를 찾아냅니다.
C++ 구현 예제
다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.
#include <bits/stdc++.h>
using namespace std;
set<string> st;
bool isaVowel(char c);
bool isaConsonant(char c);
void findSubSequence(string str);
int main(){
string s = "abekns";
findSubSequence(s);
cout<<"The substring generated are :\n";
for (auto i : st)
cout<<i<<" ";
cout << endl;
return 0;
}
bool isaVowel(char c) {
return (c=='a'||c=='e'||c=='i'||c=='o'||c=='u');
}
bool isaConsonant(char c) {
return !isaVowel(c);
}
void findSubSequence(string str) {
for (int i = 0; i < str.length(); i++) {
if (isaVowel(str[i])) {
for (int j = str.length() - 1; j >= i; j--) {
if (isaConsonant(str[j])) {
string str_sub = str.substr(i, j + 1);
st.insert(str_sub);
for (int k = 1; k < str_sub.length() - 1; k++){
string sb = str_sub;
sb.erase(sb.begin() + k);
findSubSequence(sb);
}
}
}
}
}
}
코드 설명
- isaVowel(): 매개변수로 받은 문자가 a, e, i, o, u 중 하나라면 true를 반환하여 해당 문자가 모음임을 알려줍니다.
- isaConsonant(): 모음이 아닌 모든 문자는 자음이므로, isaVowel()의 결과에 NOT 연산을 적용해 반환합니다.
- findSubSequence(): 바깥쪽 반복문으로 모음 위치(i)를 고정하고, 안쪽 반복문으로는 문자열 끝부터 자음 위치(j)를 역순으로 탐색합니다. 모음과 자음 쌍을 찾으면 두 인덱스 사이의 부분 문자열을 set에 저장한 뒤, 중간에 있는 문자를 하나씩 제거한 문자열에 대해 스스로를 재귀 호출하여 더 짧은 부분 시퀀스까지 모두 탐색합니다.
- set<string>을 사용하기 때문에 중복된 결과는 자동으로 제거되며, 최종 결과는 사전순으로 정렬되어 출력됩니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 부분 시퀀스가 생성됩니다.
ab abek abekn abekns abeks aben abens abes abk abkn abkns abks abn abns abs aek aekn aekns aeks aen aens aes ak akn akns aks an ans as ek ekn ekns eks en ens es
이 방식은 재귀 호출을 통해 가능한 모든 부분 시퀀스를 탐색하므로, 최악의 경우 시간 복잡도가 O(2n)에 가깝게 증가할 수 있습니다. 따라서 이 접근 방법은 입력 문자열의 길이가 비교적 짧은 경우에 적합합니다.