leetcode - gray code(java)

level - medium

[문제 내용]
연속된 수가 1개의 비트만 다른, 즉 그레이코드를 반환하라.
범위는 0~2^n-1(1<=n<=16)

[example 1]

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

[example 2]

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

[해결 방법]
n = 2 일 경우

00, 01, 11, 10

n = 3 일 경우

000, 001, 011, 010, 110, 111, 101, 100

여기서 규칙을 찾을 수 있는데,

00 -> 0 / 1
01 -> 1 / 0
11 -> 0 / 1
10 -> 1 / 0

위와 같은 규칙으로 움직인다는 것을 볼 수 있다.

000, 001, 011, 010, 110, 111, 101, 100

위의 규칙을 활용하여 문제를 해결했다.

class Solution {
    public List<Integer> grayCode(int n) {
        if(n == 1) {
            ArrayList<Integer> result = new ArrayList<>();
            result.add(0);
            result.add(1);
            return result;
        }

        String[] base = new String[]{"00", "10", "11", "01"};
        ArrayList<String> list = new ArrayList<>();
        Collections.addAll(list, base);
        for(int i=2; i<n; i++) {
            ArrayList<String> buffer = new ArrayList<>();
            for(int j=0; j<list.size(); j++) {
                String binary = list.get(j);
                if(j % 2 == 0) {
                    buffer.add(binary+"0");
                    buffer.add(binary+"1");
                } else {
                    buffer.add(binary+"1");
                    buffer.add(binary+"0");
                }
            }
            list = buffer;
        }
        
        ArrayList<Integer> result = new ArrayList<>();
        for(String binary : list) {
            result.add(Integer.parseInt(binary, 2));
        }
        
        return result;
    }
}