[LeetCode]/[Easy]

[Top Interview Questions] 190. Reverse Bits

위대한먼지 2023. 6. 8. 22:00

정답)

class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for _ in range(32):
            res = (res<<1) + (n&1)
            n>>=1
        return res

정답출처

문제)

문제출처

 

32비트의 정수가 주어졌을 때 그 정수의 비트들을 뒤집어 전환시키시오.

 

예시 1)

n = 00000010100101000001111010011100

output = 964176192 (00111001011110000010100101000000)

 

예시 2)

n = 11111111111111111111111111111101

output = 3221225471 (10111111111111111111111111111111)

 

제한)

인풋의 길이는 32입니다.

 

도전)

만약 이 함수가 계속해서 실행된다면 어떻게 최적화하시겠습니까?

풀이)

이번 문제는 비트 연산을 이용합니다. 저도 비트 연산을 이용해 풀긴 했지만 다른 답안들을 보니 조금 더 깔끔하고 똑똑하게 쓰인 정답이 있어 MrShobhit의 답안을 이용했습니다.

 

아웃풋 변수 res에 n의 맨 끝자리부터 하나씩 붙여줄 겁니다.

 

<<을 이용하여 res를 왼쪽으로 한 칸 땡기고 그 빈칸에 n의 끝자리 숫자를 붙입니다.

그리고 >>을 이용하여 n을 오른쪽을 한 칸 땡겨 다음 n의 끝자리 숫자를 구할 수 있도록 해 줍니다.

 

>>와 <<이 정확히 무엇을 하는지는 아래 설명에서 조금 더 자세하게 다루겠습니다.

 

def reverseBits(self, n: int) -> int:
        res 변수

        32번 동안:
            res를 왼쪽으로 한 칸 땡기고 n의 끝자리 숫자를 붙여줌
            n을 오른쪽으로 한 칸 땡겨줌
            
        res를 리턴

Shift Operator)

>>와 <<을 shift operator라고 부릅니다. 말 그대로 비트를 오른쪽/왼쪽으로 이동(shift) 시켜주는 연산자이죠.

 

예를 들어 10001 >> 1을 하면

10001을 오른쪽으로 한 칸 움직이게 한다는 뜻입니다.

 

10001 >> 1    ->    01000

 

10001 >> 3을 하면

10001을 오른쪽으로 세 칸 움직이게 해 줍니다.

 

10001 >> 3    ->    00010

 

 

<<도 똑같겠죠?

10110 << 1    ->    01100

10110 << 2    ->    11000

 

이것만 이해하시면 바로 코드로 가시죠.

코드)

정답을 저장해 줄 변수 res에 0을 저장해 줍니다.

 

그리고 제한에서 n의 길이는 32라고 했으니 for문을 32번 실행시켜 줍니다.

 

원리는 res를 왼쪽으로 한 칸 땡기고 거기서 생긴 빈 한 칸에 n의 맨 뒷 끝자리 숫자를 더해줍니다.

 

& 연산자의 테이블은 다음과 같습니다.

x y x&y
0 0 0
0 1 0
1 0 0
1 1 1

만약 x의 값 그대로 받고 싶을 때 x&1을 해주면 x의 값 그대로 받는 것을 확인하실 수 있습니다.

0&1 = 0

1&1 = 1

 

고로 n&1을 하면 n의 끝 자리 숫자를 알 수 있죠.

 

10001 & 1

이렇게 res의 오른쪽 빈칸에 새로운 n의 끝자리 숫자를 더해서 res를 업데이트시켜 줬다면

이제는 n을 업데이트해줘야 합니다.

 

저희가 구하고 싶은 n의 끝자리 숫자는 구했기 때문에 n의 다음 숫자를 구하기 위해서 n을 오른쪽으로 한 칸 땡깁니다.

 

10001 >>= 1

이렇게 32번 반복해서 n을 성공적으로 변환시켰다면 res를 리턴합니다.

 

 

저희가 쉽게 생각하기 위해서 비트의 관점에서 본거지만 사실 실제로 리턴되는 값은 비트가 아니라 10진수의 정수입니다. 

왜냐하면 연산 중에만 비트가 사용되는 거지 연산 후에는 다시 10진수의 정수의 관점으로 보는 것이기 때문입니다.

 

class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        
        for _ in range(32):
            res = (res<<1) + (n&1)
            n>>=1
        return res

 

 

오늘도 새로운 비트 연산자가 나왔네요! 문제가 조금 불친절하게 설명이 되어있는 것 같은데 하시다 보면 뭘 요구하는지 알게 되는 것 같습니다. 아마 저처럼 n을 오른쪽으로 땡기실 생각은 많이들 하셨겠지만 이 사람처럼 res 또한 왼쪽으로 땡길 생각은 못하셨을 것 같습니다. 정말 기발하네요 ㅎㅎ. 

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)

저작자표시 비영리 변경금지