LeetCode 89(Gray Code, Python)

1. 문제 링크

• https://leetcode.com/problems/gray-code/description/

Gray Code - LeetCode

 

2. 문제 설명

• n-bit gray code sequence는 아래 조건을 만족하는 2^n의 정수 sequence를 의미한다.
  • 모든 integer는 [0, 2^n -1] range에 포함되어 있어야 한다.
  • 가장 첫번째 정수는 0이다.
  • 각 정수는 sequence에서 한번 씩만 등장한다.
  • 인접한 정수들의 binary representation은 정확하게 1 bit 차이만 존재해야 한다.
  • 그리고 첫번째와 마지막 정수의 binary representation 또한 정확히 1 bit 차이만 존재해야 한다.
• 예시1) n=2 라면, output = [0,1,3,2]
  • 설명: [0,1,3,2]에 대한 binary representation은 [00,01,11,10]인데,
    • 여기서 00과 01은 1bit 차이, 01과 11 또한 1bit 차이, 10과 00 또한 1bit 차이가 나기 때문
    • 물론, [0,2,3,1] 또한 조건을 만족하므로 답은 중복이 될 수 있다.
• 예시2) n=1이라면, output =[0,1]이 된다.

3. 처음 풀이

• 비트 연산자가 익숙하지 않아서, 우선 규칙을 찾아보았다. 
• 몇가지 케이스를 보니  
  • n=1일 때, [0,1]
  • n=2일 때, [0,1,3,2]
  • n=3일 때, [0,1,3,2,6,7,5,4] 등으로 규칙이 나오고,
  • 이는 n=k일 때의 sequence는 n=k-1일 때의 sequence에 추가로, 해당 시퀀스를 역순으로 한 뒤 2^(n-1)를 더한 sequence를 추가한것과 동일하다는 규칙이 등장하였고, 
• 이에 재귀를 써서, return하는 구조로 코드를 작성하였다. 

class Solution:
    def grayCode(self, n: int) -> List[int]:
        if n ==1:
            return [0,1]
        else: 
            return self.grayCode(n-1) + [i+2**(n-1) for i in self.grayCode(n-1)[::-1]]

4. 다른 풀이 

• 비트 연산자를 활용한 풀이
• i >> 1을 한다는 것은 비트를 오른쪽으로 한 칸 이동시킨다는 뜻
  • 예를 들어 이진법 1000에 1칸 오른쪽으로 이동하면 100이 됨 
  • 이걸 원래와 XOR연산 (^) 한 것은 기존값과 bit 1만큼 차이가 나게 되고, 
  • 이를 계속 append하여 return하는 구조

class Solution:
    def grayCode(self, n: int) -> List[int]:
        result = []
        for i in range(2 ** n):
            result.append((i >> 1) ^ i)
        return result

 

5. 배운 점

• 비트 연산의 이용
• gray code는 연속된 수가 한 비트씩만 차이나기 때문에 아날로그 신호처럼 연속적인 신호가 입력될 때 신뢰성이 높다. 전송 오류로 갑자기 값이 튀면 바로 알아차릴 수 있기 때문이다. 하드디스크 드라이브 등에 이용하였다.
• 또한 순차적으로 값이 증감하는 경우에 한 bit만 변경하면 되므로 속도가 빠르다.
• gray code는 유일한가? 몇가지를 만들 수 있지? 수학 문제도 낼 수 있겠다.