C++로 한 문자열의 문자들을 사용해 다른 문자열을 최대 몇 개 만들 수 있는지 계산하는 방법

두 문자열 str_1과 str_2가 입력으로 주어졌을 때, str_1에 포함된 문자들을 각각 한 번씩만 사용하여 str_2와 동일한 문자열을 최대 몇 개 만들 수 있는지 그 개수를 구하는 것이 목표입니다.

참고 − 두 문자열의 모든 알파벳은 대소문자가 서로 일치한다고 가정합니다.

구체적인 예시를 통해 이해해 보겠습니다.

예시 1

입력 − str_1 = "abcaaaabca", str_2 = "bca"

출력 − 생성 가능한 문자열의 발생 횟수: 2

설명 − str_1 안에는 "bca"에 해당하는 조합이 두 곳에 존재합니다.

str_1[1-3]="bca" 와 str_1[7-9]="bca"

예시 2

입력 − str_1 = "about", str_2 = "cout"

출력 − 생성 가능한 문자열의 발생 횟수: 0

설명 − str_1에는 "cout"를 만드는 데 필요한 문자 조합이 존재하지 않습니다.

문제 해결 접근 방식

핵심 아이디어는 각 알파벳의 등장 빈도를 비교하는 것입니다. 먼저 str_1의 모든 알파벳 빈도를 배열 arr_1[26]에 저장하고, str_2의 모든 알파벳 빈도를 배열 arr_2[26]에 저장합니다.

두 문자열 str_1과 str_2를 입력받고, 각각의 길이를 str_1.size()와 str_2.size()로 계산합니다.
함수 count_string(string str_1, int len_str_1, string str_2, int len_str_2)는 두 문자열과 그 길이를 인자로 받아, str_1의 문자들로 만들 수 있는 str_2의 최대 개수를 반환합니다.
초기 count 값을 INT_MAX로 설정합니다.
str_1의 문자 빈도를 담을 arr_1[26]과 str_2의 문자 빈도를 담을 arr_2[26]을 0으로 초기화합니다.
for 반복문을 사용해 str_1과 str_2를 각각 순회하며 arr_1과 arr_2의 빈도 값을 갱신합니다.
다시 for 반복문으로 arr_2를 순회하면서, 현재 빈도 arr_2[i]가 0이 아니라면 count(이전 값)와 arr_1[i] / arr_2[i] 중 더 작은 값을 count에 저장합니다. 즉, str_1의 각 알파벳은 str_2의 해당 문자 하나를 만드는 데 딱 한 번만 사용됩니다.
모든 반복이 끝나면 count에는 str_1과 str_2에서 대응되는 문자들의 매칭 가능 횟수 중 최솟값이 남게 됩니다. 예를 들어 aaabbbb(a=3개, b=4개)와 abb(a=1개, b=2개)의 경우, 최종 count는 1이 됩니다.
마지막으로 count를 반환하면 그것이 바로 원하는 결과입니다.

코드 예제

#include <bits/stdc++.h>
using namespace std;
int count_string(string str_1, int length_str_1, string str_2, int length_str_2){
    int count = INT_MAX;
    int arr_1[26] = { 0 };
    int arr_2[26] = { 0 };
    for (int i = 0; i < length_str_1; i++){
        arr_1[str_1[i] - 'a']++;
    }
    for (int i = 0; i < length_str_2; i++){
        arr_2[str_2[i] - 'a']++;
    }
    int total_alphabets = 26;
    for (int i = 0; i < total_alphabets; i++){
        if(arr_2[i]){
            count = min(count, arr_1[i] / arr_2[i]);
        }
    }
    return count;
}
int main(){
    string str_1 = "knowledge", str_2 = "know";
    int length_str_1 = str_1.size();
    int length_str_2 = str_2.size();
    cout<<"Count occurrences of a string that can be constructed from another given string are: "<<count_string(str_1,length_str_1, str_2, length_str_2);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −

Count occurrences of a string that can be constructed from another given string are: 1

즉, "knowledge"라는 문자열의 문자들을 각각 한 번씩만 사용하여 "know"를 정확히 1개 만들 수 있다는 의미입니다. 이 방법은 시간 복잡도 O(N + M)(N, M은 각 문자열의 길이)로 매우 효율적으로 문제를 해결할 수 있습니다.