[LeetCode] 779. K-th Symbol in Grammar

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

K-th Symbol in Grammar - LeetCode

leetcode - K-th Symbol in Grammar

문제 유형 : 재귀 / 비트마스킹

문제 난이도 : Medium

 

문제

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 occurrence of 1 with 10.

• For example, for n = 3, the 1st row is 0, the 2nd row is 01, and the 3rd row is 0110.

Given two integer n and k, return the kth (1-indexed) symbol in the nth row of a table of n rows.

 

풀이

순수하게 재귀로 문자열을 생성하는 식으로 직접 구하면, 시간초과에 걸린다.

 

1행에서는 0, 2행에서는 0 | 1, 3행에서는 01 | 10, 4행에서는 0110 | 1001입니다.

가운데를 기준으로 값이 뒤집어짐을 알 수 있습니다.

이 패턴에 따르면, 절반씩 자르면서 문자열의 길이를 줄여나가면서 더 간단하게 풀 수 있습니다.

 

이러한 패턴을 따라 k번째 요소를 찾기 위해서는 현재 위치가 어느 그룹에 속하는지를 확인해야 합니다.

그리고 이 그룹에 따라 값이 뒤집히거나 그대로 남아있습니다.

k가 현재 행의 왼쪽 그룹에 속한다면,

    그 그룹은 이전 행의 왼쪽 그룹과 동일합니다. 따라서 k 값을 그대로 유지합니다.

반면, k가 현재 행의 오른쪽 그룹에 속한다면,

    그 그룹은 이전 행의 오른쪽 그룹과 동일합니다. 따라서 k를 현재 행의 길이를 반으로 나눈 값만큼 빼줍니다.

이러한 과정을 현재 행의 길이가 1이 될 때까지 반복합니다.

그런 후, 현재 위치가 어느 그룹에 속하느냐에 따라 '0' 또는 '1'을 반환합니다. 초기 값은 '0'으로 설정됩니다.

 

 

코드

C++

class Solution {
public:
    int kthGrammar(int n, int k) {
        bool flag = true;
        n = pow(2, n-1);

        while(n != 1) {
            n /= 2;

            if(k > n) {
                k -= n;
                flag = !flag;
            }
        }

        return flag?0:1;
    }
};