[LeetCode] 779. K-th Symbol in Grammar

Chobby·2일 전

JavaScript js ts typescript 기술 기초 면접 문제 알고리즘 연습 이직 코딩 코테 테스트 풀이 프로그래밍

LeetCode

목록 보기

1134/1135

행을 만들지 않고 푸는 문제임.

문제

1행에 0을 씀. 다음 행부터는 이전 행을 보고 0은 01로, 1은 10으로 바꿔 적음.

행 1: 0
행 2: 01
행 3: 0110
행 4: 01101001

n행의 k번째(1-indexed) 글자를 반환하면 됨. 제약은 1 <= n <= 30, 1 <= k <= 2^(n-1).

처음 제출한 풀이 (오답)

function kthGrammar(n: number, k: number): number {
    function recursive(prev: string, prevRow: number) {
        if (prevRow === n) return prev
        const bitNot = [...String(prev)].map(bit => bit === '1' ? '0' : '1')
        return recursive(prev + bitNot, prevRow + 1)
    }
    let result = Number(recursive('', 0))
    for (let i = 1; ; i++) {
        if (i === k) return result % 10
        result = Math.floor(result / 10)
    }
}

n행 전체를 문자열로 만든 뒤 k번째 글자를 꺼내려 한 코드인데, 세 군데가 깨져 있음.

1. 항상 0을 반환함. recursive('', 0)이 빈 문자열로 시작함. bitNot도 빈 배열이라 '' + []는 그대로 ''. 30번을 돌아도 ''이고 Number('')는 0임. 답이 0인 케이스만 우연히 통과함. 초기값이 '0'이어야 함.

2. 초기값을 고쳐도 안 돌아감. n이 30이면 행 길이가 2^29, 약 5억 자임. 문자열 메모리도 문제지만 Number()는 2^53을 넘는 순간 정밀도를 잃음. 자릿수를 /10으로 깎아 내려가는 접근 자체가 성립하지 않음.

3. 인덱스 방향이 반대임. k는 왼쪽부터 세는 번호인데 /10 루프는 오른쪽 끝부터 셈.

정리하면 행을 실제로 만드는 순간 이 문제는 풀리지 않음. 방향을 바꿔야 함.

관찰 1: 모든 자리에는 부모가 하나 있음

한 행이 다음 행으로 갈 때 글자 하나가 두 글자로 늘어남. 즉 이진 트리임.

행 3:    0     1     1     0
        / \   / \   / \   / \
행 4:  0 1   1 0   1 0   0 1

4행의 6번째 글자는 3행의 3번째 글자에서 나왔음. 일반화하면 부모 위치는 ceil(k / 2).

관찰 2: 부모를 알면 자식 값이 바로 나옴

부모가 무엇이든 자식 쌍은 두 가지뿐임.

부모가 0 이면 자식은  0 1
부모가 1 이면 자식은  1 0

부모	왼쪽 자식	오른쪽 자식
0	0 (같음)	1 (반대)
1	1 (같음)	0 (반대)

왼쪽 자식은 언제나 부모와 같고, 오른쪽 자식은 언제나 부모의 반대임. 그리고 내가 어느 쪽 자식인지는 k의 홀짝이 알려줌.

k가 홀수 → 왼쪽 자식 → 부모와 같은 값
k가 짝수 → 오른쪽 자식 → 부모의 반대 값

풀이

두 관찰을 그대로 코드로 옮기면 끝임.

function kthGrammar(n: number, k: number): number {
    if (n === 1) return 0                          // 꼭대기는 무조건 0
    const parent = kthGrammar(n - 1, Math.ceil(k / 2))
    return k % 2 === 0 ? 1 - parent : parent       // 짝수면 뒤집기
}

한 번 호출할 때마다 한 행씩 위로 올라가므로 호출 깊이는 최대 30. 시간 O(n), 공간 O(n)이고 행은 한 글자도 만들지 않음.

동작 추적: `n = 2, k = 2`

행 1:      0          ← 1행 1번째
          / \
         /   \
행 2:   0     1       ← 찾는 것은 2행 2번째
       k=1   k=2

kthGrammar(2,2)  ─내려감→  ceil(2/2) = 1  →  kthGrammar(1,1)
                                               ↓ n === 1 이므로 return 0
kthGrammar(2,2)  ←올라옴─  parent = 0
                            k = 2, 짝수 = 오른쪽 자식 → 1 - 0 = 1

답은 1. 내려갈 때는 위치만 계산하고, 꼭대기에 닿은 뒤 되돌아 올라오면서 값이 확정되는 구조임.

동작 추적: `n = 4, k = 6`

kthGrammar(4,6)  → 부모 (3,3), k=6 짝수 → 뒤집을 예정
kthGrammar(3,3)  → 부모 (2,2), k=3 홀수 → 그대로
kthGrammar(2,2)  → 부모 (1,1), k=2 짝수 → 뒤집을 예정
kthGrammar(1,1)  = 0

되돌아 올라오며 계산
(1,1) = 0
(2,2) = 뒤집기 → 1
(3,3) = 그대로 → 1
(4,6) = 뒤집기 → 0

4행은 01101001이고 6번째 글자는 0. 일치함.

한 걸음 더: 재귀도 없애기

위 추적에서 실제로 한 일은 "뒤집기를 몇 번 했나"를 세는 것뿐임. 시작값이 0이므로 값 자체는 볼 필요가 없고, 뒤집은 횟수가 홀수면 1, 짝수면 0임.

그렇다면 뒤집는 횟수는 어떻게 한 번에 셀까. k를 0부터 세는 번호(k - 1)로 바꿔 2진수로 적으면, 그 비트열이 꼭대기에서 내려온 경로 그 자체임. 0이면 왼쪽, 1이면 오른쪽.

k = 6이면 k - 1 = 5 = 101(2):

행 1:  0                시작
 └ 1 → 오른쪽 : 뒤집기   (0 → 1)
 └ 0 → 왼쪽   : 그대로   (1)
 └ 1 → 오른쪽 : 뒤집기   (1 → 0)
행 4:  0

오른쪽으로 꺾은 횟수 = k - 1의 1비트 개수. 따라서 답은 그 패리티(홀짝)임.

function kthGrammar(n: number, k: number): number {
    let x = k - 1, bit = 0
    while (x) {
        bit ^= x & 1    // 끝 비트가 1이면 토글
        x >>>= 1        // 한 칸 밀어 다음 비트로
    }
    return bit
}