graycode 시퀀스 출력하기

방금 정말 어이없는 코드를 봤다..

 

일단 문제를 보자

Gray Code - LeetCode

Gray Code - LeetCode

 

graycode를 이진수문자열 말고 그냥 10진수 정수 시퀀스로 출력하는 문제다.

보통 graycode는 기존 시퀀스를 뒤집고 앞을 반전시키고 뭐 그러면서 푼다.

깔끔한 예제

public List<Integer> grayCode(int n) {
    List<Integer> rs=new ArrayList<Integer>();
    rs.add(0);
    for(int i=0;i<n;i++){
        int size=rs.size();
        for(int k=size-1;k>=0;k--)
            rs.add(rs.get(k) | 1<<i);
    }
    return rs;
}

 

파이썬으로 바꾸면

gc = [0]

for i in range(n):

   for j in range(len(gc)-1,-1,-1):

      gc.append(gc[j] | 1<<i)

return gc

 

이정도 느낌.

이것도 잘푼거다 ㅋㅋ

근데 이렇게 푸니까 웬걸 memory usage가 중위권이라는 것이다.

그래서 메모리 usage가 적은 상위권 사람들의 코드를 봤다 어떻게 풀었는지.

놀라지마시라.

 

for i in range(2**n):
    yield i ^ i>>1

 

??????????

??????????????????

???????

그니까... 0-indexed 시퀀스라고 가정했을 때 i번째 인덱스의 graycode는 i ^ i>>1이다.

 

어이가 없네 진짜..ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

bit manipulation 알고리즘은 보통 bit단위의 패턴 발견을 통해 디자인한다.

0부터 시작하는 숫자들의 이진수와 graycode sequence의 이진수를 나란히 놓고 보면 규칙이 보일것이다.

 

yield는.. 솔루션 함수가 리스트를 리턴하도록 되어있으니 어차피 정답체크툴이 솔루션 함수 리턴값가지고 iteration을 돌면서 정답을 체크할거란것을 이용한거다. 그래서 yield로 공간절약을..ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 진짜 입이 떡벌어진다. 천재다 천재ㅋㅋㅋㅋㅋ