문제 소개
이 튜토리얼에서는 주어진 문자열로 시작하고 끝나는 부분 문자열의 총 개수를 구하는 프로그램을 작성해 보겠습니다.
하나의 문자열과 두 개의 부분 문자열이 주어집니다. 우리가 해야 할 일은 시작 문자열로 시작하고 끝 문자열로 끝나는 서로 다른 부분 문자열의 개수를 세는 것입니다. 먼저 예시를 살펴보며 문제를 이해해 보겠습니다.
입력
str = "getmesomecoffee"
start = "m"
end = "e"
출력
6
주어진 문자열에서 조건을 만족하는 서로 다른 부분 문자열은 총 6개입니다. 바로 me, mesome, mesomemecoffe, mesomemecoffee, mecoffe, mecoffee입니다.
문제 해결 단계
문자열들을 초기화합니다.
전체 문자열을 순회하면서 시작 문자열과 끝 문자열이 나타나는 인덱스를 찾아 각각 별도의 배열에 저장합니다.
서로 다른 부분 문자열을 저장하기 위한 set을 초기화합니다.
전체 문자열을 다시 순회합니다.
현재 인덱스가 앞서 만든 배열에서 시작 문자열 위치와 일치하는지 확인합니다.
시작 문자열의 인덱스를 찾았다면, 그 지점부터 끝 문자열을 탐색합니다.
끝 문자열을 만날 때까지 문자를 하나씩 변수에 누적합니다.
끝 문자열을 발견하면 부분 문자열 개수를 증가시키고, 해당 부분 문자열을 set에 추가합니다.
부분 문자열 변수를 초기화하여 다음 탐색을 준비합니다.
최종 부분 문자열 개수를 출력합니다.
C++ 구현 예제
그럼 실제 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int getSubstringsCount(string str, string start, string end) {
int substrings_count = 0, str_length = str.size(), start_length = start.size(), end_length = end.size();
int start_matches_index[str_length] = {0}, end_matches_index[str_length] = {0};
for (int i = 0; i < str_length; i++) {
if (str.substr(i, start_length) == start) {
start_matches_index[i] = 1;
}
if (str.substr(i, end_length) == end) {
end_matches_index[i] = 1;
}
}
set<string> substrings;
string current_substring = "";
for (int i = 0; i < str_length; i++) {
if (start_matches_index[i]) {
for (int j = i; j < str_length; j++) {
if (!end_matches_index[j]) {
current_substring += str[j];
}
if (end_matches_index[j]) {
current_substring += str.substr(j, end_length);
if (substrings.find(current_substring) == substrings.end()) {
substrings_count++;
}
substrings.insert(current_substring);
}
}
current_substring = "";
}
}
return substrings_count;
}
int main() {
string str = "getmesomecoffee";
string start = "m";
string end = "e";
cout << getSubstringsCount(str, start, end) << endl;
return 0;
}
코드 설명
getSubstringsCount 함수는 크게 두 단계로 동작합니다. 첫 번째 반복문에서는 전체 문자열을 훑으며 시작 문자열과 끝 문자열이 등장하는 위치를 각각 불리언 배열(start_matches_index, end_matches_index)에 기록합니다. 두 번째 반복문에서는 시작 위치를 발견할 때마다 내부 반복문을 돌려 끝 문자열까지의 부분 문자열을 만들고, set에 존재하지 않는 새로운 부분 문자열인 경우에만 개수를 증가시킵니다. set을 활용하기 때문에 중복된 부분 문자열은 자동으로 걸러집니다.
이 알고리즘의 시간 복잡도는 중첩 반복문으로 인해 대략 O(n²)이며, 여기에 set 탐색·삽입 연산의 로그 시간이 추가로 소요됩니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.
6
마무리
이번 튜토리얼에서는 주어진 문자열로 시작하고 끝나는 서로 다른 부분 문자열의 개수를 구하는 방법을 알아보았습니다. 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요.