

앨리스와 밥은 게임을 하고 있습니다. 처음에 앨리스는 문자열 단어 = "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);
}
}
Share article