문자열 게임에서 K번째 문자 이해하기 (단계별) - LeetCode 3304

Source: Dev.to

문제 요약

Alice와 Bob이 게임을 하고 있습니다. 처음에 Alice는 문자열

word = "a"

을 가지고 있습니다.

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

Bob은 다음 작업을 무한히 반복하도록 Alice에게 요청합니다:

word의 각 문자를 영어 알파벳에서 다음 문자로 바꾸고, 그 결과 문자열을 원래 word 뒤에 붙여 새로운 문자열을 만든다.

작업 예시

• "c" → "cd"
• "zb" → "zbac"

word의 길이가 최소 k가 될 때까지 작업을 수행한 뒤, k번째 문자의 값을 반환합니다.

예시 1

입력: k = 5
출력: "b"

설명

word = "a"
1번째 작업:  "b" 생성   → word = "ab"
2번째 작업:  "bc" 생성  → word = "abbc"
3번째 작업:  "bccd" 생성→ word = "abbcbccd"

5번째 문자는 'b'입니다.

예시 2

입력: k = 10
출력: "c"

제약 조건

1 ≤ k ≤ 500

각 작업은 문자열을 다음과 같이 변형합니다

new_word = old_word + shifted(old_word)

여기서 shifted(old_word)는 모든 문자를 다음 알파벳 문자로 바꾸는 것을 의미합니다 ('a' → 'b', …, 'z' → 'a').
길이는 매 단계마다 두 배가 됩니다: 1 → 2 → 4 → 8 → 16 → ….
전체 문자열을 만들지 않고 k번째 문자를 구해야 합니다.

---

🧠 핵심 통찰

각 단계마다

S(n) = S(n‑1) + shifted(S(n‑1))

• 첫 번째 절반 → 이전 문자열 S(n‑1)
• 두 번째 절반 → shifted(S(n‑1))

따라서 임의의 인덱스 k에 대해:

• k가 첫 번째 절반에 있으면, 이전 단계에서 같은 인덱스 k의 문자와 동일합니다.
• k가 두 번째 절반에 있으면, (k – half)를 이전 단계의 인덱스로 매핑한 뒤 그 문자를 +1(모듈로 26)만큼 이동시킵니다.

---

✅ 재귀 구현 (Java)

public class Solution {
    public char KthCharacter(int k) {
        return solve(k);
    }

    private char solve(int k) {
        if (k == 1) return 'a';

        // Find the smallest power of two ≥ k
        int length = 1;
        while (length > 1;    // half = length / 2

        // k is in the second half → recurse on the mirrored index
        char prev = solve(k - half);
        // shift by one position in the alphabet (wrap around at 'z')
        return (char)('a' + (prev - 'a' + 1) % 26);
    }
}

재귀는 k == 1이 될 때 멈추며, 기본 문자 'a'를 반환합니다.
두 번째 절반에 들어갈 때마다 알파벳을 한 칸씩 이동시킵니다.

---

🔍 단계별 예시 (k = 6)

재귀 풀기

• solve(2): 'a'를 한 칸 이동 → 'b'
• solve(6): 'b'를 한 칸 이동 → 'c'

결과: 'c'

---

🧠 메모리에서 일어나는 일

k = 6에 대한 호출 스택:

solve(6)
  → solve(2)
      → solve(1)

재귀가 되돌아올 때마다 두 번째 절반 호출에서 알파벳 이동을 한 번씩 적용해 최종 문자를 얻습니다.

---

⏱ 시간 및 공간 복잡도

• 시간: O(log k) – 각 재귀 단계마다 문제 크기가 절반으로 줄어듭니다.
• 공간: O(log k) – 재귀 스택 깊이만큼 사용됩니다.

---

🔥 최종 요점

전체 문자열을 만들 필요가 없습니다. k를 반복적으로 줄이고 두 번째 절반에 들어간 횟수를 세면, 간단한 분할‑정복 재귀(또는 동등한 반복 버전)로 원하는 문자를 계산할 수 있습니다. 이 방법은 로그 시간에 실행되며 보조 공간도 로그 수준만 사용합니다.