[LeetCode] 89. Gray Code

문제 출처: https://leetcode.com/problems/gray-code/

Gray Code - LeetCode

문제

n-bit Gray Code 시퀀스는 다음의 규칙을 따르는 정수 2^n개의 시퀀스이다:

• 모든 정수는 [0, 2^n - 1]의 범위의 수이다.
• 첫 번째 정수는 0 이다.
• 각 정수는 시퀀스 내에서 한 번만 등장한다.
• 모든 인접한 정수 쌍 사이의 이진수는 정확히 1개의 비트가 다르다.
• 첫 번째와 마지막 정수의 이진수는 정확히 1개의 비트가 다르다.

정수 n이 주어질 때, 아무 유효한 n-bit Gray Code 시퀀스를 반환하라.

예제

Input: n = 2
Output: [0,1,3,2]

Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

Input: n = 1
Output: [0,1]

풀이

나열된 gray code 사이의 어떤 순서가 존재하는지 여부를 확인해보기 위해서 n = 1, n = 2인 케이스를 이진수로 나열해보자.

n = 1
0:    0
1:    1 

n = 2
0:    00
1:    01
3:    11
2:    10

현재까지는 어떤 패턴이 존재하는지 알기 어려우니, n = 3일 때를 추가 나열해보면 아래와 같다.

n = 3
0:    000
1:    001
3:    011
2:    010
6:    110
7:    111
5:    101
4:    100

이제 위 3가지 케이스를 토대로 눈에 보이는 규칙들을 찾아보자.

 

1차적으로 눈에 보이는 것은 n = 3일 때의 케이스 중 절반은 n = 2일 때의 케이스와 같고, n = 2일 때의 케이스 중 절반은 n = 1일 때의 케이스와 동일하다는 것이다.

 

그다음으로 보이는 것은 맨 앞자리의 비트값이다. 순차적으로 2^(n-1)개는 0, 그 다음 2^(n-1)개는 1로 되어 있다는 점이 눈에 들어온다.

 

또 하나 눈에 들어오는 점은, 맨 앞 자리 비트를 떼어내고 보면, 윗 절반과 아래 절반 사이에 역순이라는 관계가 존재함을 알 수 있다.

현재까지 찾은 규칙을 토대로 해답을 구하는 방식에 대해 생각해보면 다음과 같다.

1. n-1비트의 gray code의 시퀀스를 구한다.
2. 1에서 구한 시퀀스의 각 숫자 맨 앞에 0을 붙인다.
3. 1에서 구한 시퀀스의 순서를 뒤집은 배열을 구한다.
4. 3에서 구한 시퀀스의 각 숫자 맨 앞에 1을 붙인다.
5. 2와 4에서 구한 두 개의 시퀀스를 합치고, 각 값은 10진수로 변경한다.

n-1비트의 gray code를 찾는 것을 재귀 방식으로 구한다면, 아래와 같은 코드로 문제의 해답을 찾을 수 있다.

var grayCode = function(n) {
    function recursive(n) {
        if (n == 1) { return ['0', '1']; }

        const preGrayCode = recursive(n-1);

        const ans = [];

        for (let i = 0; i < preGrayCode.length; i++) {
            ans.push('0' + preGrayCode[i]);
        }
        for (let i = preGrayCode.length-1; i >= 0; i--) {
            ans.push('1' + preGrayCode[i]);
        }

        return ans;
    }

    return recursive(n).map(val => parseInt(val, 2));
}

이러한 복잡한 방법을 사용하지 않아도 손쉽게 gray code를 계산하는 방법이 있는데, 위키디피디아의 내용을 참조하였으며, 다음과 같이 코드를 간략화시킬 수 있다.

var grayCode = function(n) {
    const ans = [];

    for (let i = 0; i < Math.pow(2, n); i++) {
        ans.push(i ^ (i >> 1));
    }

    return ans;
};

짧게나마 정리하자면, 구하고자 하는 결과가 결국 1 ~ n까지의 수를 순차적으로 gray code로 변환하는 것과 동일하고 특정 정수 값을 gray code로의 변환하는 과정은 num ^ (num >> 1) 을 통해서 구할 수 있으므로 위와 같은 과정을 통해 답을 얻을 수 있는 것이다.

 

 

Github: 89.js

opwe37/Algorithm-Study