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 )
'코드' 카테고리의 다른 글
Design Circular Queue (0) | 2019.11.01 |
---|---|
Unique Binary Search Trees II (0) | 2019.10.25 |
Merge Two Sorted Lists (0) | 2019.10.24 |
Pow(x, n) (0) | 2019.10.24 |
Maximum Depth of Binary Tree (0) | 2019.10.24 |