본문으로 건너뛰기

3335 - Total Characters in String After Transformations I

info

풀이 키워드​

스포주의

DP


풀이 코드​

info
  • 메모리: 45500 KB
  • 시간: 97 ms
class Solution {
    final int MOD = 1_000_000_007;

    public int lengthAfterTransformations(String s, int t) {
        int[] dp = new int[26];
        int[] nxt = new int[26];

        // init: if t == 0 then length = 1
        for (int ch = 0; ch < 26; ++ch) dp[ch] = 1;

        while (t-- > 0) {
            for (int ch = 0; ch < 26; ++ch) {
                if (ch == 25) { // cnt('z') <- cnt('a') + cnt('b')
                    nxt[ch] = (dp[0] + dp[1]) % MOD;
                } else {
                    nxt[ch] = dp[ch+1];
                }
            }

            int[] tmp = dp;
            dp = nxt;
            nxt = tmp;
        }

        long ans = 0;
        for (char ch : s.toCharArray()) {
            ans = (ans + dp[ch-'a']) % MOD;
        }

        return (int) ans;
    }
}

풀이 해설​

z를 제외한 나머지 알파벳은 +1씩 값이 변경되고 (ex. a -> b, x -> y)

z는 ab로 변경된다는 조건 하에, 주어진 문자열을 t만큼 변경해서 그 길이를 구하는 문제이다.

길이 확장 조건이 동적이라서 특정 공식으로 도출하기 어렵다.


caution

응 아니야​

다음의 내용들은 오답에서 정답까지의 과정을 다루고 있다. (재실수 방지 목적)

❌ 이진 확장 -> WA​

a ~ z까지는 글자수 변동 없이 내용만 바뀌고

t의 26주기 시점에서만 z -> ab로 글자수가 2배 확장되는 점을 고려해서 이진 확장인가 싶었다.

따라서 s의 한 글자씩 순회하면서 해당 글자가 t 이후에 얼마나 확장될지를 공식화했고

1 << n/26 으로 구해진다고 생각했다. (단, n = t + 'a'로부터의 오프셋)


하지만 잘 생각해보면 z -> aa 가 아니고 z -> ab라서 확장 주기가 일정치 않다.

z는 +26 시점에서 ab -> zab로 b만 확장되어 2글자가 아닌 3글자가 되고

+27이 되어야 ab -> abbc로 4글자가 된다. 하지만 이렇게 또 서로 다른 오프셋때문에 다음 주기에도 확장 타이밍이 글자마다 제각각이 된다.

마찬가지로 기존 도출된 공식으로 계산하면 y는 2바퀴째인 +52 시점부터 오답이 나옴을 확인할 수 있다.

👉 결론적으로, 해당 접근은 틀렸다.

WA 코드
import java.math.*;

class Solution {
    public int lengthAfterTransformations(String s, int t) {
        // a(1) -> ab(2) -> abbc(4) -> abbcbccd(8)
        // 2^0  ->  2^1  ->   2^2   ->    2^3
        //  0   ->   26  ->   26*2  ->   26*3
        final int MOD = 1_000_000_007;
        long sum = 0;
        for (char ch : s.toCharArray()) {
            int offset = ch - 'a'; // offset: required t to transform 'a' into ch
            int n = t + offset;
            int res = BigInteger.ONE.shiftLeft(n/26).mod(BigInteger.valueOf(MOD)).intValue();
            sum += res % MOD;
        }

        return (int) sum;
    }
}
WA TC
"jqktcurgdvlibczdsvnsg"
7517

❌ 하향식 DP -> TLE1​

공식화가 안되는데다 캐싱의 여지가 있으니 차선책인 DP로 접근했다.

메모이제이션으로 각 알파벳의 t별 길이를 캐싱했는데 함수 호출 오버헤드 때문인지 제약조건의 상한에서 TLE가 터졌다.

TLE1 코드
class Solution {
    final int MOD = 1_000_000_007;
    int memo[][] = new int[26][100_001];

    public long dp(int ch, int t) {
        if (t == 0) return 1;
        if (memo[ch][t] != 0) return memo[ch][t];

        long res = 0L;
        if (ch == 25) res = (dp(0, t-1) + dp(1, t-1)) % MOD;
        else res = dp(ch+1, t-1) % MOD;

        return memo[ch][t] = (int) res;
    }

    public int lengthAfterTransformations(String s, int t) {
        long ans = 0L;
        for (char ch : s.toCharArray()) ans = (ans + dp(ch-'a', t)) % MOD;
        return (int) ans;
    }
}
TLE1 TC
{a만으로 구성된 길이 10만의 문자열}
100000

❌ 상향식 DP -> TLE2​

하향식으로 TLE를 받아서 호출 오버헤드가 없는 상향식으로 고쳤는데 역시나 TLE였다.

왜지?? 하고 정보를 찾아보니 메모이제이션을 2차원으로 정의한게 원인이었다.

C/C++에선 그냥 스택 메모리에 할당하면 다 충분히 빠른데

자바는 2차원 배열이 객체배열 + 내부배열 구조이고, 힙 메모리에 위치해있어 더 느리다.

그리고 메모리 접근 지역성의 관점에서도 CPU caching + prefetch가 들어가는 1D는 2D와 아주 큰 퍼포먼스 차이를 낼 수 있다.

그러므로 자바에서의 dp 연산은
⭐2D 배열을 n개의 1D 배열로 치환⭐하여

각 배열을 주소로 스왑해서 쓰는게 훨 빠르다는 결론.

하지만 1D나 2D나 시간복잡도는 동일하다.

둘 다 O(26×t×∣s∣)O(26 \times t \times |s|) 이다. 😥

보통 알고리즘 자체의 복잡도 선에서 정답 컷을 내는데 메모리 병목 차이로 정답이 갈리는게 다소 읭스럽긴 하다.

TLE2 코드
class Solution {
    final int MOD = 1_000_000_007;
    long dp[][] = new long[26][100_001];

    public int lengthAfterTransformations(String s, int t) {
        for (int i = 0; i < 26; ++i) dp[i][0] = 1;
        for (int j = 1; j < t+1; ++j) {
            for (int i = 0; i < 26; ++i) {
                if (i == 25) dp[i][j] = (dp[0][j-1] + dp[1][j-1]) % MOD;
                else dp[i][j] = dp[i+1][j-1];
            }
        }

        long ans = 0L;
        for (char ch : s.toCharArray()) ans = (ans + dp[ch-'a'][t]) % MOD;
        return (int) ans;
    }
}
TLE2 TC
"rssjmowborzlmeqqqobyqcejqloqicrzuioahtgvdfptpdiofqnnximowhqovyqxhclnokkvqjwsrftkyerwnbecbmanninbgwwkglezhocqjwgzlqddzojmiohtkqdrmjiowbfvtzrqtzmkcfmivdiqqqueacibannstgtvqsijncxchwbfdvmqlzfinhijodevmabkcubwzwhyytfbveefesyayesszwgmzyurpzyjohvywngbtokwequjxcjyoeyoarnlopivfuenhzounucgeuawoxgqvixmlpjmqbvmtunksququawvbmwzyftijgkmkzxhqjleoblkyfdcycsnzvriygckuaxwendcmgfbrnggsozmhxmdpiuuopgfnxekoyfnlhzctdkfdwzbrdjxrvqqnasaqvtdrcqcgfdmpxakujbsrmcintncablupxhtzsqivaetfcufmxsmugzzmkhlachvgemgwrrhevzzpsqjvhgyalfpnxbfxhyglxfhfvbpbypyourftcowtnsykcadbqufdzihzsjylccmjohjajyejuwnosiovynbosxewxhksoszumnfmapjuvkmenmtanjbrldmfrlvoofdtluktbwwzavxxsbcrsvpbzbpqdutasuiowhmtgowvghndncmhrusxgfrjrcrqwrvtlvpxdfydeqyzowxxgrpgrzrotpaxhcrrpoeuomoxklvgdfdnhbgwpolpwfuscyvlkpbamwcbmqoofplzevjkspktcjanfglhygtfbqxagnqtpgfhpkqgnywzvckdbbyfmyklxpwqsslctqerxgxwumoxvetprjrmttxdjyarbjucsaanhmxknqlnanqzmzearndgslboqubuxmvhwcrnqhuoiebalcsaektkbzwztkaluhecfpwvzdzjyfzevxroclrdqwlxjxuadsntsbidptxrlwjyzubzflxllsntjcbxexciujwcqbljistpyaepabpophyhxhzfgbavxwsaodglknjgnbqspreylgaiziqzhyeafdubhvtfgflkcgwhsocjhywnqjvqqwxdoymzfskibejnwarqpjyootzvqfgqzavutozkzebfvbagtsgpkreraifogvyaxjrukcxnwurpnpmmyqcsegkiakepsvxgpillpzsuonmixasdjbpzmblkgjaiwmlmqoxaameqrcawskfqsjccxeqlwuxczhtxwgcojiofqkttffaflpuihwpg"
3434

메모​

  • 이 문제도 릿코 댓글이 웃김 ㅋㅋ
  • WA -> TLE1 -> TLE2 거치면서 그라데이션으로 혈압이 올랐다.
    • C#도 잘만 2D로 통과하는데 언어 스펙에서 이렇게 구린거 처음 봄;
  • 더 deep하게 보려면 JIT 디버깅 (2D 구조가 JIT 최적화를 어렵게 한다고 함) + JMH 벤치마킹 비교까지 들어가야 한다.
  • t 범위때문에 DP 배제해놓고 봤는데 다시 생각하니 10610^6 미만이니까 괜찮았던 듯?