이 문제에서는 'a'와 'b'로만 구성된 문자열 str과 정수 N이 주어집니다. 주어진 문자열을 N번 반복하여 이어 붙여 새로운 문자열을 만들었을 때, 그 안에서 'a'의 개수가 'b'의 개수보다 많은 부분 문자열의 총 개수를 구하는 것이 우리의 과제입니다.
문제 예시
예제를 통해 문제를 자세히 살펴보겠습니다.
입력: aab 2 출력: 9 설명: 생성된 문자열은 "aabaab"입니다. 'a' 개수가 'b'보다 많은 부분 문자열: 'a', 'aa', 'aab', 'aaba', 'aabaa', 'aabaab', 'aba', 'baa', 'abaa'
접근 방법
이 문제를 해결하려면 반복해서 만들어진 전체 문자열이 아니라, 원본 문자열 str 자체의 접두사를 기준으로 검사해야 합니다. 각 위치까지 읽으면서 'a'와 'b'의 누적 개수를 비교하고, 'a'가 더 많은 시점마다 유효한 접두사(부분 문자열)가 하나씩 만들어진다고 볼 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 원본 문자열을 한 번 순회하며 각 접두사에서 'a'의 개수가 'b'보다 많은 경우의 수를 셉니다.
- 한 번의 순회에서 조건을 만족하는 접두사가 없거나 N이 1이라면, 추가 계산 없이 현재 카운트가 곧 답입니다.
- 모든 접두사가 조건을 만족하거나 'a'와 'b'의 개수 차이가 0이라면, 결과는 단순히
카운트 × N이 됩니다. - 그 외의 경우에는 문자열을 반복해서 이어 붙일 때마다 새로 생기는 유효한 접두사의 수를 누적합니다. 이때 어느 반복에서도 새로운 유효 접두사가 생기지 않으면 중단하고, 모든 접두사가 유효하다면 남은 반복 횟수를 한꺼번에 곱해 마무리합니다.
이러한 방식으로 전체 문자열을 실제로 N번 이어 붙이지 않고도 효율적으로 정답을 구할 수 있습니다.
C++ 구현 예제
아래 프로그램은 위에서 설명한 해결 방법을 구현한 것입니다.
#include <iostream>
#include <string.h>
using namespace std;
int prefixCount(string str, int n){
int a = 0, b = 0, count = 0;
int i = 0;
int len = str.size();
for (i = 0; i < len; i++) {
if (str[i] == 'a')
a++;
if (str[i] == 'b')
b++;
if (a > b) {
count++;
}
}
if (count == 0 || n == 1) {
cout<<count;
return 0;
}
if (count == len || a - b == 0) {
cout<<(count*n);
return 0;
}
int n2 = n - 1, count2 = 0;
while (n2 != 0) {
for (i = 0; i < len; i++) {
if (str[i] == 'a')
a++;
if (str[i] == 'b')
b++;
if (a > b)
count2++;
}
count += count2;
n2--;
if (count2 == 0)
break;
if (count2 == len) {
count += (n2 * count2);
break;
}
count2 = 0;
}
return count;
}
int main() {
string str = "aba";
int N = 2;
cout<<"The string created by using '"<<str<<"' "<<N<<" times has ";
cout<<prefixCount(str, N)<<" substring with count of a greater than count of b";
return 0;
}실행 결과
The string created by using 'aba' 2 times has 5 substring with count of a greater than count of b
위 실행 결과에서 알 수 있듯이, 문자열 "aba"를 2번 반복해 만든 "abaaba"에는 'a'의 개수가 'b'보다 많은 부분 문자열이 총 5개 존재합니다.