K-th Symbol in Grammar

0부터 시작한다. 다음 줄부터는 0은 01로 1은 10으로 바꿔나간다.

 

이 때 줄의 개수 N이 주어질 때, K번째 항목이 뭔지 알아맞춰야 한다. 인덱스가 1부터 시작하니 주의.

 

트리의 깊이에 따라 패턴이 발견된다. 즉 왼쪽 노드는 부모와 값이 같고 오른쪽 노드는 반전된다. 이 점을 이용한다.

왼쪽 노드는 그대로이고 오른쪽 노드는 항상 반전된다

# https://leetcode.com/problems/k-th-symbol-in-grammar/discuss/113710/Python-simple-solution-to-understand-with
# -explanations
class Solution:
    def kthGrammar( self, N: int, K: int ) -> int:
        if N == 1:
            return 0

        return self.__kthGrammer( N - 1, K )


    def __kthGrammer( self, N, K ):
        if N == 1:
            if K == 1:
                return 0
            else:
                return 1

        halfPoint = (2 ** N) // 2

        if K <= halfPoint:
            return self.__kthGrammer( N - 1, K )
        else:
            result = self.__kthGrammer( N - 1, K - halfPoint )

            return int( not result )