문제 개요
이 문제에서는 하나의 문자열이 주어지며, 주어진 문자열에서 조건에 맞는 부분 문자열을 찾아야 합니다. 찾아야 할 부분 문자열은 모음(vowel)으로 시작하여 자음(consonant)으로 끝나야 합니다.
문자열(string)이란 문자들이 순서대로 나열된 배열이라고 할 수 있습니다.
이 문제에서 생성해야 하는 부분 수열은 원본 문자열에서 일부 문자를 삭제하는 방식으로 만들 수 있으며, 이때 문자들의 순서는 절대 변경되지 않아야 합니다.
입력: 'abc' 출력: ab, ac, abc
이 문제를 해결하기 위해서는 문자열을 순회하면서 모음 위치를 고정한 뒤, 그 뒤에 이어지는 수열들을 검사하는 방식을 사용할 수 있습니다. 아래 알고리즘을 통해 해결 과정을 살펴보겠습니다.
알고리즘
1단계: 변수 i를 이용해 문자열의 각 문자를 순회합니다. 2단계: i번째 문자가 모음인지 확인합니다. 3단계: j번째 문자가 자음인지 확인합니다. 4단계: 첫 번째 문자부터 j번째 문자까지의 부분 문자열을 HashSet에 추가합니다. 5단계: 위 과정을 반복하며 문자열에서 부분 문자열을 찾아냅니다.
반복적(iterative) 접근 방식에서는 문자열 전체를 대상으로 순회를 수행합니다. 탐색 범위는 1부터 2len(문자열)-1까지입니다.
여기서 핵심 아이디어는 비트마스크(bitmask) 기법입니다. 1부터 2ⁿ-1까지의 각 정수를 이진수로 표현하면, 비트가 1로 설정된 위치의 문자들을 선택함으로써 해당 정수에 대응하는 고유한 부분 수열을 얻을 수 있습니다. 예를 들어 n=4일 때 정수 5(이진수 0101)는 2번째와 4번째 문자를 선택한 부분 수열에 해당합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
string subString(string s, int binary){
string sub = "";
int pos;
while(binary>0){
pos=log2(binary&-binary)+1;
sub=s[pos-1]+sub;
binary= (binary & ~(1 << (pos-1)));
}
reverse(sub.begin(),sub.end());
return sub;
}
void findAllSubStrings(string s){
map<int, set<string> > sorted_subsequence;
int len = s.size();
int limit = pow(2, len);
for (int i = 1; i <= limit - 1; i++) {
string sub = subString(s, i);
sorted_subsequence[sub.length()].insert(sub);
}
for (auto it : sorted_subsequence) {
for (auto ii : it.second)
cout<<ii<<" ";
cout<<"\t";
}
}
int main() {
string s = "wxyz";
cout<<"The substring are :\n";
findAllSubStrings(s);
return 0;
}출력 결과
프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
w x y z wx wy wz xy xz yz wxy wxz wyz xyz wxyz
코드 설명
subString 함수는 정수형 비트마스크 값을 받아, 해당 비트가 켜져 있는 위치의 문자들만 모아 하나의 부분 문자열을 만듭니다. 여기서 binary & -binary 연산은 가장 낮은 자리에 설정된 비트만 남기는 기법으로, log2 함수와 함께 사용하면 해당 비트의 위치를 빠르게 계산할 수 있습니다.
findAllSubStrings 함수는 1부터 2ⁿ-1까지의 모든 정수에 대해 부분 수열을 생성하고, map과 set을 활용해 길이별로 사전순 정렬된 상태로 저장한 뒤 출력합니다. 덕분에 결과가 길이 순으로 깔끔하게 정렬되어 표시됩니다.