Skip to content

leet code

1675 - K-th Symbol in Grammar

가장 쉽고 간단한 방법으로 풀려고 시도 했으나 TLE 에러가 났습니다.

약 10분 정도 소요

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int kthGrammar(int n, int k) {
        return int(genString("0", n).at(k-1) - 0x30);
    }

    string genString(string s, int n)
    {
        if(n==1)
            return s;

        string rslt ="";
        for(int i=0; i<s.size(); ++i)
        {
            if(s[i] == '0')
                rslt += "01";
            else
                rslt += "10";
        }

        return genString(rslt, n-1);
    }

};
  • 다음 시도

bit 조작으로 빠르게 계산. (약간 수식이 틀렸음. 수정 예정)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int kthGrammar(int n, int k) {
        if(k==1) return 0;
        max_cnt = n;
        printf("aaaa: %d\n", ((int)pow(2, n-1) - k));
        return genString(0, 1) & ((int)pow(2, n-1) - k+1) && 1;
    }

    uint genString(uint a, uint n)
    {
        printf("a: %d, n: %d\n", a, n);
        if(max_cnt == n) return a;
        printf("current: %d, next: %d + %d = %d\n", a, (a*(uint)pow(2, n)), ((~a) & (1 << (n-1))), (a*(uint)pow(2, n)) + ((~a) & (1 << (n-1))));
        return genString((a*(uint)pow(2, n+1)) + ((~a) & (1 << (n-1))), n+1);
    }

private:
    int max_cnt = 0;
};
  • 최종 제출. time beats 100%, space beats 78.90%

string을 전부 생성한 후에 index를 찾아들어가는 것은 효율이 좋지 않았습니다.

string을 생성하지 않는 방향으로 코드를 수정했고, 통과했습니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int kthGrammar(int n, int k) {
        if(k==1) return 0;
        return solve(n, k-1);
    }

    int solve(int n, int k)
    {
        if(n==2) // 종료 조건
        {
            if(k%2)
                return 1;
            else
                return 0;
        }
        if(k >= pow2(n-2))
        {
            return !solve(n-1, k%pow2(n-2));
        }else
        {
            return solve(n-1, k);
        }
    }

    int pow2(int n)
    {
        int result = 1;
        while(n--)
        {
            result *= 2;
        }

        return result;
    }
};