[LeetCode/Typescript] 779. K-th Symbol in Grammar

https://leetcode.com/problems/k-th-symbol-in-grammar/

K-th Symbol in Grammar - LeetCode

n = 1일 경우 0부터 시작해, n이 1일 증가할 때 마다 0은 01로 1은 10으로 바뀝니다.

 

n = 2일 경우 0이 01로 바뀌어 01,

n = 3일 경우 0이 01로 바뀌고 1이 10으로 바뀌어 0110 이 됩니다.

 

패턴을 찾기 위해 5번째까지 써보면

 

n = 1, 0

n = 2, 01

n = 3, 0110

n = 4, 01101001

n = 5, 0110100110010110

 

가 됩니다.

 

제가 처음 시도한 방법은 아래 코드와 같습니다.

n = 5일 때의 문자열인 01101001 10010010 은 n = 4일 때의 문자열을 한번 적고, 그것을 반대로 적은 것과 같습니다.

거기에 메모이제이션을 썼지만 문자열 자체가 너무 길어 에러가 발생했습니다.

const cache = Array.from({length:31}, () => Array.from({length:2}, () => ""));
cache[1][0] = "0";
cache[1][1] = "0";
cache[2][0] = "01";
cache[2][1] = "10";

function kthGrammar(n: number, k: number): number {

    const getString = (n: number, r: boolean): string => {
        const check = cache[n][r ? 1 : 0] === "" ? "" : cache[n][r ? 1 : 0];
        const reverseCheck = cache[n][r ? 0 : 1] === "" ? "" : cache[n][r ? 0 : 1];

        const string = check !== "" ? check : cache[n][r ? 1 : 0] = getString(n - 1, r);
        const reverse = reverseCheck !== "" ? reverseCheck : cache[n][r ? 0 : 1] = getString(n - 1, !r);

        return string + reverse;
    }

    return +getString(n, false)[k - 1];
};

 

n = 1, 0

n = 2, 01

n = 3, 0110

n = 4, 01101001

 

모든 문자열을 미리 구하는 것으로는 풀 수 없는 문제였고, 다른 방식으로 문제에 접근했습니다.

n이 2일 경우와 3인 경우에 각 문자열 간의 값을 비교해보았습니다.

n = 3, k = 4일 경우, n = 2, k = 2의 문자와 다릅니다.

n = 3, k = 3일 경우, n = 2, k = 2의 문자와 같습니다.

n = 3, k = 2일 경우, n = 2, k = 1의 문자와 다릅니다.

n = 3, k = 1일 경우, n = 2, k = 1의 문자와 같습니다.

 

k 가 짝수일 경우, f(n - 1, k // 2)를 뒤집은(0이면 1, 1이면 0) 값과 같고,

홀수일 경우 f(n - 1, k // 2)의 값과 같습니다.

 

그것을 코드로 써보면 아래와 같습니다.

기저 조건은 n이 1일 경우와 2인 경우까지 작성해줍니다.

function kthGrammar(n: number, k: number): number {
  const getNum = (n: number, k: number): number => {
    if (n === 1) return 0;
    if (n === 2) return k - 1;

    if (k % 2 === 0) return getNum(n - 1, Math.ceil(k / 2)) === 1 ? 0 : 1;
    return getNum(n - 1, Math.ceil(k / 2));
  };

  return getNum(n, k);
}