[JAVA 문제 풀이] 363. Find the K-th Character in String Game II [스트링 게임 II에서 K번째 캐릭터 찾기]

Find the K-th Character in String Game II - LeetCode

Can you solve this real interview question? Find the K-th Character in String Game II - Alice and Bob are playing a game. Initially, Alice has a string word = "a". You are given a positive integer k. You are also given an integer array operations, where operations[i] represents the type of the ith operation. Now Bob will ask Alice to perform all operations in sequence: * If operations[i] == 0, append a copy of word to itself. * If operations[i] == 1, generate a new string by changing each character in word to its next character in the English alphabet, and append it to the original word. For example, performing the operation on "c" generates "cd" and performing the operation on "zb" generates "zbac". Return the value of the kth character in word after performing all the operations. Note that the character 'z' can be changed to 'a' in the second type of operation.   Example 1: Input: k = 5, operations = [0,0,0] Output: "a" Explanation: Initially, word == "a". Alice performs the three operations as follows: * Appends "a" to "a", word becomes "aa". * Appends "aa" to "aa", word becomes "aaaa". * Appends "aaaa" to "aaaa", word becomes "aaaaaaaa". Example 2: Input: k = 10, operations = [0,1,0,1] Output: "b" Explanation: Initially, word == "a". Alice performs the four operations as follows: * Appends "a" to "a", word becomes "aa". * Appends "bb" to "aa", word becomes "aabb". * Appends "aabb" to "aabb", word becomes "aabbaabb". * Appends "bbccbbcc" to "aabbaabb", word becomes "aabbaabbbbccbbcc".   Constraints: * 1 <= k <= 1014 * 1 <= operations.length <= 100 * operations[i] is either 0 or 1. * The input is generated such that word has at least k characters after all operations.

https://leetcode.com/problems/find-the-k-th-character-in-string-game-ii/description

앨리스와 밥은 게임을 하고 있습니다.
처음에 앨리스는 문자열 단어 = "a"를 가지고 있습니다.

양의 정수 k가 주어집니다. 또한 정수 배열 연산도 주어지는데,
여기서 연산 [i]는 i번째 연산의 유형을 나타냅니다.

이제 밥은 앨리스에게 모든 작업을 순차적으로 수행하도록 요청할 것입니다:

* operations[i] == 0인 경우 단어 사본을 추가합니다.
* operations[i] == 1인 경우, 단어의 각 문자를 영어 알파벳의 다음 문자로 변경하여 새 문자열을 생성하고 원래 단어에 추가합니다.
	예를 들어, "c"에서 연산을 수행하면 "cd"가 생성되고 "zb"에서 연산을 수행하면 "zbac"이 생성됩니다.
모든 작업을 수행한 후 단어로 k번째 문자의 값을 반환합니다.

두 번째 유형의 작업에서는 문자 'z'를 'a'로 변경할 수 있습니다.

제약 조건:

1 <= k <= 1014
1 <= operations.length <= 100
operations [i]는 0 또는 1입니다.
입력은 모든 연산 후에 단어가 최소 k개의 문자를 가지도록 생성됩니다.

내가 작성한 코드

class Solution {
    public char kthCharacter(long k, int[] operations) {
        int n = operations.length;
        long[] lens = new long[n + 1]; // 각 단계별 문자열 길이를 저장할 배열
        lens[0] = 1; // 초기 문자열은 "a" → 길이 1

        // 1. lens 배열 채우기
        for (int i = 0; i < n; i++) {
            // 곱셈이 long 범위를 넘지 않도록 오버플로우 방지
            if (lens[i] > Long.MAX_VALUE / 2) {
                lens[i + 1] = Long.MAX_VALUE; // 최대값으로 고정
            } else {
                lens[i + 1] = lens[i] * 2; // 문자열 길이 2배 증가
            }
        }

        // 2. k번째 문자가 어디서 유래했는지 역추적
        // 왼쪽 >> 기존 문자열
        // 오른쪽 >> 이전 문자열의 복사본에 shift 적용된 문자열
        int shiftSum = 0; // 최종적으로 'a'에 더해질 누적 shift 값

        // operations를 뒤에서부터 역추적
        for (int i = n - 1; i >= 0; i--) {
            if (k > lens[i]) {
                // 현재 k는 오른쪽 절반(shift된 복사본)에서 온 문자라는 뜻
                k -= lens[i]; // 왼쪽 기준으로 인덱스 보정
                shiftSum = (shiftSum + operations[i]) % 26; // 누적 shift (알파벳은 26자니까 mod 26)
            }
            // 왼쪽에서 왔으면 k 그대로 두고 shiftSum도 증가시키지 않음
        }

        // 최종적으로 남은 k는 최초 문자열 'a'에서 시작된 문자 위치
        // 'a'에 누적된 shiftSum 만큼 더해서 결과 문자 반환
        return (char) ('a' + shiftSum);
    }
}