Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 푸는 최소 문자열 변환 문제: 재배열 후 필요한 최소 변경 횟수

같은 길이를 가진 두 개의 소문자 문자열 s와 t가 주어집니다. 먼저 s를 임의의 순서로 재배열(rearrange)한 다음, s를 t로 만들기 위해 필요한 최소 변경 횟수를 구하는 것이 이 문제의 목표입니다.

문제 예시

입력이 s = "eccynue", t = "science"라고 가정해 보겠습니다. 이 경우 출력은 2가 됩니다.

그 이유는 다음과 같습니다. 먼저 "eccynue"를 "yccence"로 재배열하면, 이후 y를 s로 바꾸고 두 번째 c를 i로 바꾸는 두 번의 변경만으로 "science"를 만들 수 있기 때문입니다.

해결 접근 방법

이 문제는 문자 빈도수(frequency) 계산만으로 간단히 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • s에서 어떤 문자의 개수가 t보다 많다면, 그 초과분만큼 반드시 다른 문자로 변경해야 합니다.
  • 반대로 s에 부족한 문자는 재배열 과정에서 이미 고려되므로, 초과분만 세면 됩니다.

구체적인 알고리즘 단계는 다음과 같습니다.

  1. 결괏값을 저장할 변수 ret을 0으로 초기화합니다.
  2. s의 알파벳 빈도수를 저장하는 배열 cnt1(크기 26)과, t의 빈도수를 저장하는 배열 cnt2(크기 26)를 정의합니다.
  3. i를 0부터 25까지 순회하면서 각 알파벳에 대해 max(cnt1[i] − cnt2[i], 0) 값을 ret에 더합니다.
  4. 모든 순회가 끝나면 ret을 반환합니다. 이것이 곧 최소 변경 횟수입니다.

C++ 구현 예제

아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int solve(string s, string t) {
        int ret = 0;
        vector <int> cnt1(26);
        vector <int> cnt2(26);
        for(int i = 0; i < s.size(); i++){
            cnt1[s[i] - 'a']++;
        }
        for(int i = 0; i < t.size(); i++){
            cnt2[t[i] - 'a']++;
        }
        for(int i = 0; i < 26; i++){
            ret += max(cnt1[i] - cnt2[i], 0);
        }
        return ret;
    }
};
int main(){
    Solution ob;
    cout << (ob.solve("eccynue", "science"));
}

입력

"eccynue", "science"

출력

2

복잡도 분석

이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이로, 두 문자열을 한 번씩 순회하여 빈도수를 계산하기 때문입니다. 공간 복잡도는 알파벳 개수에 해당하는 크기 26의 배열 두 개만 사용하므로 O(1)로 상수 공간입니다.