2023.10.25 Today's Challenge

fabichoi 2023. 10. 25. 23:45

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

K-th Symbol in Grammar - LeetCode

Can you solve this real interview question? K-th Symbol in Grammar - We build a table of n rows (1-indexed). We start by writing 0 in the 1st row. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each o

leetcode.com

덮어놓고 배열을 만들다간 TL이 날 것 같은 문제.
솔루션을 보니 2진 트리로 만들어서 dfs 돌리는 방법 소개함.
더 놀라웠던건 수학적으로 증명하면 2줄로 마무리 됨 -_-;

class Solution:
    def dfs(self, n, k, root):
        if n == 1:
            return root
        
        total = 2 ** (n-1)

        if k > (total / 2):
            next_root = 1 if root == 0 else 0
            return self.dfs(n-1, k-(total/2), next_root)
        else:
            next_root = 0 if root == 0 else 1
            return self.dfs(n-1, k, next_root)
        
    def kthGrammar(self, n: int, k: int) -> int:
        return self.dfs(n, k, 0)