C++에서 각 문자를 최대 한 번씩 사용해 다른 문자열로부터 만들 수 있는 문자열 개수 구하기

두 개의 문자열 str_1과 str_2가 주어졌을 때, str_1에 포함된 문자들을 각각 최대 한 번씩만 사용하여 str_2를 온전히 몇 세트 만들어 낼 수 있는지 개수를 계산하는 문제입니다. 즉, str_1의 문자를 중복 없이 소진해 가면서 str_2가 총 몇 번 완성되는지 확인해야 합니다.

입력 · 출력 예시

예제 1

입력 - str_1 = "technical learning", str_2 = "learning"

출력 - 각 문자를 최대 한 번씩 사용하여 다른 문자열로부터 만들 수 있는 문자열의 개수: 1

설명 - str_2인 "learning"을 구성하는 데 필요한 모든 문자가 str_1 안에 정확히 한 세트만 존재합니다. 따라서 만들 수 있는 개수는 1입니다.

예제 2

입력 - str_1 = "ellohsehelloabcoelhl", str_2 = "hello"

출력 - 각 문자를 최대 한 번씩 사용하여 다른 문자열로부터 만들 수 있는 문자열의 개수: 3

설명 - str_1을 자세히 살펴보면 'l'이 6개, 'e'가 4개, 'h'가 3개, 'o'가 3개 포함되어 있습니다. "hello"를 한 번 만들 때마다 'l'은 2개씩 필요하므로, 최대 3세트까지 만들 수 있습니다. 따라서 정답은 3입니다.

풀이 접근 방식

문자열 str_1과 str_2를 입력받고 각각의 길이를 계산한 뒤, 이후 처리를 위해 함수에 전달합니다.
str_2를 몇 번 만들 수 있는지 저장할 임시 변수 count를 선언하고 INT_MAX로 초기화합니다. INT_MAX는 C++에서 변수가 가질 수 있는 최댓값(+2147483647)을 나타내는 상수로, 여기서는 '최솟값 찾기'의 시작점 역할을 합니다.
영어 알파벳은 총 26자이므로 크기가 26인 배열을 생성하고 0으로 초기화합니다.
첫 번째 반복문을 0부터 str_1의 길이까지 돌면서 arr[str_1[i] - 'a'] 값을 1씩 증가시켜, str_1에 각 알파벳이 몇 번 등장하는지 기록합니다.
두 번째 반복문을 0부터 str_2의 길이까지 돌면서, str_2를 만드는 데 필요한 문자별 개수를 별도 배열에 저장합니다.
마지막으로 26개의 알파벳을 순회하며 count를 "보유 개수 ÷ 필요 개수"의 최솟값으로 갱신합니다. 이 값이 곧 str_2를 완성할 수 있는 최대 세트 수입니다.
count를 반환하고 결과를 출력합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// str_1의 각 문자를 최대 한 번씩만 사용해
// str_2를 몇 세트 완성할 수 있는지 반환하는 함수
int atmost_once(string str_1, string str_2){
    int count = INT_MAX;
    int arr[26]  = { 0 };   // str_1의 문자별 보유 개수
    int need[26] = { 0 };   // str_2의 문자별 필요 개수

    for (int i = 0; i < (int)str_1.length(); i++){
        arr[str_1[i] - 'a'] += 1;
    }
    for (int i = 0; i < (int)str_2.length(); i++){
        need[str_2[i] - 'a'] += 1;
    }
    for (int i = 0; i < 26; i++){
        if (need[i] > 0){
            // 각 문자로 만들 수 있는 세트 수 중 가장 작은 값 유지
            count = min(count, arr[i] / need[i]);
        }
    }
    return count;
}

int main(){
    string str_1 = "technical learning";
    string str_2 = "learning";
    cout << "각 문자를 최대 한 번씩 사용해 다른 문자열로 만들 수 있는 문자열의 개수: "
         << atmost_once(str_1, str_2);
    return 0;
}

단순히 min(count, arr[...])만 비교하는 방식은 str_2에 같은 문자가 여러 번 등장하는 경우(예: "hello"의 'l')를 정확히 처리하지 못할 수 있습니다. 위 코드처럼 필요 개수로 나눈 몫을 비교하면 어떤 입력에 대해서도 올바른 결과를 얻을 수 있습니다.

실행 결과

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

각 문자를 최대 한 번씩 사용해 다른 문자열로 만들 수 있는 문자열의 개수: 1

복잡도 분석

시간 복잡도: O(N + M) - N은 str_1의 길이, M은 str_2의 길이입니다. 두 문자열을 한 번씩 순회하고 크기 26짜리 배열을 한 번 더 확인하면 끝나기 때문입니다.
공간 복잡도: O(1) - 입력 크기와 무관하게 고정 크기(26)의 배열 두 개만 사용합니다.