LeetCode - 3337. Total Characters in String After Transformations II

문제링크

 

문제 설명

소문자로 이루어진 문자열 s, 정수 t (변환 횟수), 그리고 크기가 26인 정수 배열 nums가 주어집니다.
이때, 정확히 t번의 변환(Transformation)을 수행하게 됩니다. 각 변환은 아래 규칙에 따라 진행됩니다:

• 문자열 s의 각 문자 s[i]를 다음과 같이 변경합니다:
  • s[i] = 'a'라면 nums[0]개의 연속된 알파벳 문자로 변경됩니다.
  • 즉, s[i]는 다음 알파벳 문자부터 시작하여 nums[s[i] - 'a']개의 문자를 나열한 문자열로 대체됩니다.
    • 예: s[i] = 'a', nums[0] = 3이라면 'a' → "bcd"로 변환됩니다.
    • 예: s[i] = 'y', nums[24] = 3이라면 'y' → "zab"로 변환됩니다. (알파벳은 z 이후 a로 순환됩니다)

이 과정을 정확히 t번 반복한 뒤 생성되는 문자열의 최종 길이를 구해 주세요.
정답이 매우 클 수 있으므로, 10^9 + 7로 나눈 나머지를 반환해 주세요.

제한 사항

• 1 <= s.length <= 10^5
• s consists only of lowercase English letters.
• 1 <= t <= 10^9
• nums.length == 26
• 1 <= nums[i] <= 25

예시

Example 1:

Input: s = "abcyy", t = 2, nums = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2]

Output: 7

Explanation:

• First Transformation (t = 1):
  • 'a' becomes 'b' as nums[0] == 1
  • 'b' becomes 'c' as nums[1] == 1
  • 'c' becomes 'd' as nums[2] == 1
  • 'y' becomes 'z' as nums[24] == 1
  • 'y' becomes 'z' as nums[24] == 1
  • String after the first transformation: "bcdzz"
• Second Transformation (t = 2):
  • 'b' becomes 'c' as nums[1] == 1
  • 'c' becomes 'd' as nums[2] == 1
  • 'd' becomes 'e' as nums[3] == 1
  • 'z' becomes 'ab' as nums[25] == 2
  • 'z' becomes 'ab' as nums[25] == 2
  • String after the second transformation: "cdeabab"
• Final Length of the string: The string is "cdeabab", which has 7 characters.

Example 2:

Input: s = "azbk", t = 1, nums = [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]

Output: 8

Explanation:

• First Transformation (t = 1):
  • 'a' becomes 'bc' as nums[0] == 2
  • 'z' becomes 'ab' as nums[25] == 2
  • 'b' becomes 'cd' as nums[1] == 2
  • 'k' becomes 'lm' as nums[10] == 2
  • String after the first transformation: "bcabcdlm"
• Final Length of the string: The string is "bcabcdlm", which has 8 characters.

풀이 흐름

• 처음 읽고 LeetCode - 3335 문제에서 한 단계 더 나아간 문제라고 판단했습니다. 그래서 각 글자를 t번 변환시킨 후의 길이를 구해주면 될 거라고 판단했습니다.
• 하지만 3335번과 같이 t번의 변환 후의 값을 하나씩 계산하면 1번의 계산에도 최대 10억번의 계산을 필요로 하여 시간 제한에 걸리게 됩니다.
• 보통 문제에서 N의 개수가 10억을 넘어가면 이분 탐색일 가능성이 높다고 생각하고 이분 탐색을 적용할 수 있는 곳을 고민합니다.
• t번의 연산에서 이분 탐색을 적용하는 것을 고민하다가 1번의 변환에서 일어나는 과정을 행렬로 표현하면 t번의 변환을 M^t로 표현이 가능하여 거듭제곱을 계산하는 로직에서 logN의 시간 복잡도로 계산이 가능하단 것을 파악했습니다.
  • 예를 들어 'c' 가 다음 변환에서 'def'로 변하게 되면 matrix[2][3] = matrix[2][4] = matrix[2][5]로 표현하는 방식입니다.
• 최종 결과는 s의 각 알파벳 개수를 int[26]의 배열에 기록한 다음 (counts[0]은 'a'의 개수, counts[1]은 'b'의 개수, ...) counts와 M^t를 곱하면 최종 결과를 구할 수 있습니다.

코드

import java.util.*;

class Solution {
    int mod = 1000000007;
    public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }
        int[][] matrix = new int[26][26];
        for (int i = 0; i < 26; i++) {
            for (int j = 1; j <= nums.get(i); j++) {
                matrix[i][(i + j) % 26] = 1;
            }
        }

        int[][] matrix2 = f1(matrix, t);
        int[] result = f2(counts, matrix2);
        int ret = 0;
        for (int r : result) {
            ret = (ret + r) % mod;
        }
        return ret;
    }

    private int[][] f1(int[][] matrix, int t) {
        int[][] res = new int[26][26];
        for (int i = 0; i < 26; i++) {
            res[i][i] = 1;
        }
        while (t > 0) {
            if (t % 2 == 1) {
                res = multiply(res, matrix);
            }
            matrix = multiply(matrix, matrix);
            t /= 2;
        }
        return res;
    }

    private int[][] multiply(int[][] matrix, int[][] matrix1) {
        int[][] res = new int[26][26];
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                for (int k = 0; k < 26; k++) {
                    res[i][j] = (int) ((res[i][j] + (1L * matrix[i][k] * matrix1[k][j]) % mod) % mod);
                }
            }
        }
        return res;
    }

    private int[] f2(int[] counts, int[][] matrix) {
        int[] res = new int[26];
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                res[i] = (int) ((res[i] + (1L * counts[j] * matrix[j][i]) % mod) % mod);
            }
        }
        return res;
    }
}