[JAVA 문제 풀이] 360. Find the K-th Character in String Game I [스트링 게임 I에서 K번째 문자 찾기]

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

Can you solve this real interview question? Find the K-th Character in String Game I - Alice and Bob are playing a game. Initially, Alice has a string word = "a". You are given a positive integer k. Now Bob will ask Alice to perform the following operation forever: * 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 enough operations have been done for word to have at least k characters. Note that the character 'z' can be changed to 'a' in the operation.   Example 1: Input: k = 5 Output: "b" Explanation: Initially, word = "a". We need to do the operation three times: * Generated string is "b", word becomes "ab". * Generated string is "bc", word becomes "abbc". * Generated string is "bccd", word becomes "abbcbccd". Example 2: Input: k = 10 Output: "c"   Constraints: * 1 <= k <= 500

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

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

양의 정수 k가 주어집니다.

이제 밥은 앨리스에게 영원히 다음 작업을 수행하도록 요청할 것입니다:

단어의 각 문자를 영어 알파벳의 다음 문자로 변경하여 새 문자열을 생성하고 원래 단어에 추가합니다.

예를 들어, "c"에서 연산을 수행하면 "cd"가 생성되고 "zb"에서 연산을 수행하면 "zbac"이 생성됩니다.

단어가 최소한 k개의 문자를 가질 수 있도록 충분한 작업이 완료된 후, k번째 문자의 값을 단어로 반환합니다.

연산에서 문자 'z'를 'a'로 변경할 수 있습니다.

내가 작성한 코드

class Solution {
    public char kthCharacter(int k) {
        StringBuilder sb = new StringBuilder(); 
        sb.append("a"); // 시작 문자열은 'a'

        // k보다 긴 문자열을 만들기 위해 반복
        while(sb.length() < k) {
            StringBuilder nextSb = new StringBuilder(); // 다음 문자열을 저장할 StringBuilder

            // sb문자열의 각 문자에 대해 다음 문자를 계산
            // 'z'는 'a'로 순환되도록 처리
            for (int j = 0; j < sb.length(); j++) {
                char c = sb.charAt(j);

                if (c == 'z') {
                    nextSb.append('a');
                } else {
                    nextSb.append((char) (c + 1));
                }
            }

            sb.append(nextSb); // 다음 문자열을 현재 문자열에 추가
        }

        return sb.charAt(k - 1); 
    }
}

다른 사람의 코드

class Solution {
    public char kthCharacter(int k) {
        int ans = 0; // 몇 번 연산을 수행했는지(몇 번 다음 알파벳으로 바꿨는지) 저장
        int t; // k의 2진수에서 가장 높은 1의 비트 위치

        while (k != 1) { // k가 1이 될 때까지 반복 (맨 앞 문자까지 올라감)
            t = 31 - Integer.numberOfLeadingZeros(k); // k의 2진수에서 가장 높은 1의 위치(몇 번째 연산에서 만들어졌는지) 구함
            if ((1 << t) == k) { // k가 정확히 2의 거듭제곱(새로운 연산의 첫 문자)이면
                t--; // 바로 이전 연산의 마지막 문자로 이동
            }
            k = k - (1 << t); // k에서 해당 연산의 시작 위치(2^t)를 빼서 이전 단계로 이동
            ans++; // 연산 횟수(몇 번 알파벳을 바꿨는지) 증가
        }

        // 'a'에서 ans만큼 떨어진 알파벳(즉, k번째 문자의 값)을 반환
        return (char) ('a' + ans);
    }
}