779. K-th Symbol in Grammar

규칙성을 기반으로 생성되는 데이터의 특정 위치 값을 알아내는 문제.

첫번째 row는 0 값을 가지며 두번쨰 부터는 0 → 01, 1 → 10으로 대체하는 방식으로 다음 row를 생성한다.

처음 5개의 row를 나열해보면 아래와 같다.

["0", "01", "0110", "01101001", "0110100110010110"]

여기서 알 수 있는 규칙은 다음과 같다.

row의 번호 n 와는 관계없이 k번째 symbol이 정해진다.
n은 단순이 k 값의 범위를 제한할 뿐이다.
"0110" 이라는 패턴이 재귀적으로 반복된다.


(1) k = ~ 4^1 
	pattern: "0110"
	sub pattern: "0" → "0", "1" → "1"

(2) k = ~ 4^2
	pattern: "0110 1001 1001 0110"
	sub pattern: "0" → "0110", "1" → "1001"

(3) k = ~ 4^3
	pattern: "0110100110010110 1001011001101001 1001011001101001 0110100110010110"
	sub pattern: "0" → "0110100110010110", "1" → "1001011001101001"

위의 규칙을 살펴보면 패턴의 0에 해당되는 경우 서브 패턴의 값이 유지되며 1에 해당되는 경우 서브 패턴의 값을 반전하는 형태로 구성됨을 알 수 있다.

규칙을 바탕으로 생각해보면 다음과 같은 로직을 얻을 수 있다.

패턴 PATTERN을 정의한다.
k값을 0-base로 변경한다 --k
LSB 2 bit를 기준으로 최초 패턴에서의 값 PATTERN[k % 4]을 찾고 bit를 shift k >>= 2 한다.
k값이 0이 되기 전까지 다음을 반복한다.

LSB 2 bit를 기준으로 최초 패턴에서의 값 PATTERN[k % 4]을 찾는다.
해당 값이 0이면 현재 값을 유지하고 1이면 값을 반전 0 → 1, 1 → 0 한다.


class Solution {
public:
    const vector<int> PATTERN = {0, 1, 1, 0};
    int kthGrammar(int n, int k) {
        --k;
        int result = PATTERN[k % 4];
        k >>= 2;
        while (k > 0) {
            if (PATTERN[k % 4] == 1)
                result = result == 0? 1 : 0;
            k >>= 2;
        }
        return result;
    }
};