본문으로 건너뛰기

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

정보

풀이 키워드​

스포주의

구현


풀이 코드​

정보
  • 메모리: 42200 KB
  • 시간: 1 ms
class Solution {
    public char kthCharacter(int k) {
        int[] wordArr = new int[512]; // not 500 bc len doubles each time
        wordArr[0] = 'a';
        int len = 1;
        while (len < k) {
            for (int i = 0; i < len; ++i) {
                wordArr[len+i] = wordArr[i]+1;
            }
            len <<= 1;
        }

        return (char)wordArr[k-1];
    }
}

풀이 해설​

k번째 글자만 알아내면 되고, 이미 정해진 글자는 바뀔 일이 없기 때문에

문제에선 operation을 영원히 수행한다, 충분히 수행한다 등으로 겁주지만

그냥 operation 수행 결과의 문자열 길이가 k 이상인지만 파악해서 멈추면 된다.

한 번 operation을 수행하면 문자열의 길이가 2배씩 늘어나므로 len은 1씩 left shift 해주고,

이 때 문제에서 k는 최대 500이라고 했기 때문에 len은 512까지 늘어날 것이므로 wordArr 크기를 512로 잡아준다.

for (int i = 0; i < len; ++i) {
    wordArr[len+i] = wordArr[i]+1;
}

그리고 512 = 292^9 라서 operation 수행이 최대 9번뿐이기 때문에

문제에서 언급한 z -> a 변환은 사실 발생할 일이 없다...

그래서 for문 내에서 mod 연산은 하지 않았다.


메모​

  • 만약 StringBuilder로 구현할거라면 3ms 정도로 성능이 크게 벌어지지는 않으나, for문의 condition에 sb.length()를 사용하지 않도록 주의. 길이가 동적으로 변하므로 안됨.