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

C++ 문자열 최대 가중치 변환 알고리즘 완벽 가이드

문제 설명

'A'와 'B'로만 구성된 문자열이 주어집니다. 임의의 문자를 토글(다른 문자로 변경)하면 주어진 문자열을 다른 문자열로 변환할 수 있으며, 이렇게 만들 수 있는 변환의 수는 매우 많습니다. 이때 우리가 구해야 할 것은 가능한 변환 중 최대 가중치 변환의 가중치입니다.

문자열의 가중치는 다음 공식으로 계산됩니다.

문자열의 가중치 = 전체 쌍(pair)의 가중치 합 + 단일 문자의 가중치 합 − 총 토글 횟수

가중치 계산 규칙

  • 연속된 두 문자는 서로 다를 때만 하나의 쌍으로 간주됩니다.

  • 한 쌍의 가중치(두 문자가 서로 다른 경우) = 4

  • 단일 문자의 가중치 = 1

입출력 예시

입력 문자열이 "AA"라면 결과는 3입니다.

  • "AA"에서 파생될 수 있는 모든 변환은 "AA", "AB", "BA", "BB"입니다.

  • 최대 가중치 변환은 "AB" 또는 "BA"이며, 가중치는 "한 쌍 − 한 번의 토글" = 4 − 1 = 3입니다.

알고리즘

이 문제는 재귀 호출에 메모이제이션을 결합한 동적 계획법으로 효율적으로 해결할 수 있습니다. 각 위치에서 현재 문자를 단일 문자로 처리할지, 바로 뒤의 문자와 쌍으로 묶을지를 판단하고 두 선택지 중 더 큰 가중치를 취합니다.

1. n == 1인 경우
   maxWeight(str[0..n-1]) = 1
2. str[0] != str[1]인 경우 (서로 다른 문자로 쌍 형성)
   maxWeight(str[0..n-1]) = Max(1 + maxWeight(str[1..n-1]), 4 + getMaxRec(str[2..n-1]))
3. 그 외의 경우 (같은 문자로 쌍을 만들려면 토글 1회 필요)
   maxWeight(str[0..n-1]) = Max(1 + maxWeight(str[1..n-1]), 3 + getMaxRec(str[2..n-1]))

여기서 str[i]와 str[i+1]이 같은 문자라면 쌍을 만들기 위해 반드시 한 번의 토글이 필요하므로, 쌍 가중치 4에서 토글 비용 1을 제외한 3이 더해집니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;
int getMaxRec(string &str, int i, int n, int lookup[]){
    if (i >= n) {
        return 0;
    }
    if (lookup[i] != -1) {
        return lookup[i];
    }
    int ans = 1 + getMaxRec(str, i + 1, n, lookup);
    if (i + 1 < n) {
        if (str[i] != str[i+1]) {
            ans = max(4 + getMaxRec(str, i + 2, n, lookup), ans);
        } else {
            ans = max(3 + getMaxRec(str, i + 2, n, lookup), ans);
        }
    }
    return lookup[i] = ans;
}
int getMaxWeight(string str){
    int n = str.length();
    int lookup[n];
    memset(lookup, -1, sizeof lookup);
    return getMaxRec(str, 0, str.length(), lookup);
}
int main(){
    string str = "AA";
    cout << "Result = " << getMaxWeight(str) << endl;
    return 0;
}

코드 설명

getMaxRec 함수는 인덱스 i부터 문자열 끝까지의 최대 가중치를 재귀적으로 계산합니다. lookup 배열에 이미 계산된 결과를 저장하여 중복 연산을 제거하기 때문에 전체 시간 복잡도는 O(n)입니다. 인접한 두 문자가 서로 다르면 쌍 가중치 4를, 같으면 토글 비용을 반영한 3을 더하는 것이 핵심 로직입니다.

실행 결과

위 프로그램을 컴파일 후 실행하면 다음과 같은 출력을 얻습니다.

Result = 3