LeetCode: 89번 (Gray Code) [JAVA]

문제 링크

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

Gray Code - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 결과를 담을 List 생성 후, 초기값 0 추가
2. 주어진 n번에 대해 다음을 반복
   1) 현재 list의 사이즈를 변수로 저장
   2) 해당 위치부터 처음으로 돌아가며, 주어진 변수에 1<<n의 결과를 or로 비트 연산한 결과를 list에 추가
3. 결과 list 반환

 전체 list 속 숫자들이 한 번만 반복되며, 인근 숫자들 간에 차이점이 비트 하나씩만 바뀌어야 한다는 점에서 어렵게 느껴지긴 하지만 좀만 다르게 생각해보면 쉽게 해결할 수 있다.
 문제 해결을 위한 핵심 해결 방법은, 바로 주어진 n에 대한 결과 리스트를 만들 때, n-1에 대해 완성된 리스트를 활용하는 방법이다. 만약 n-1에 대해 주어진 조건을 만족하는 리스트가 존재한다면, 해당 리스트는 이를 뒤집어도 주어진 조건을 만족하게 된다. 만약 이 상태에서 하나의 리스트와 뒤집은 리스트를 붙이게 되면 붙는 부분의 숫자가 동일한데, 이 때 뒷 숫자의 n번째 비트를 1로 켜게 된다면, 접하는 부분의 두 숫자는 비트 하나만 달라지는 조건을 충족하게 된다. 이후 n번째 비트를 1로 켠 부분의 리스트 속 모든 요소들의 n번째 비트를 1로 켜게 된다면, 해당 리스트 속 모든 요소는 기존과 동일하게 주어진 조건을 만족하고 있다.
 이를 통해 주어진 n에 대해 조건을 만족하는 리스트를 만들 수 있는데, 우선 결과를 반환할 List를 하나 생성하고 초기값으로 0을 삽입한다. 이후 주어진 n에 대해 다음을 반복하는데, 우선 현재까지의 list 사이즈를 변수로 저장한 다음, 해당 변수를 통해 리스트의 위치부터 처음으로 돌아가며, 얻은 변수의 1<<n을 or 비트 연산으로 계산할 결과를 list에 추가하는 방식이다. 이후에는 반복이 끝난 List를 단순히 반환하면 된다.

 

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        result.add(0);//기본 0 추가

        for (int i = 0; i < n; i++) {//총 n번에 대해 반복
            int size = result.size();//기존의 list 사이즈

            for (int j = size - 1; j >= 0; j--) {//기존 list 요소를 반대로하면서, 해당 숫자의 n번 비트를 1로 변경
                result.add(result.get(j) | 1 << i);
            }
        }

        return result;
    }
}

결과