[LeetCode OJ] Reverse Bits - Easy Algorithm

<Problem Link>


<Comment>

이 문제는 두가지 해법을 작성해 보았다.

1. 파이썬에 built-in 함수를 이용한 직관적인 해법
2. 숫자를 저장하고 있는 메모리영역의 비트연산을 이용한 해법

둘다 어짜피 시간, 공간복잡도는 같다.
하지만 단일 스캔 횟수는 차이가 난다.

비트연산은 여러번 들어봤으나 그 용법은 아직도 잘 모르겟다.
나중에 좀 더 자세히 공부해봐야겟다. ㄷㄷ...

<Useful Code>

오늘 부터 파이썬의 유용한 간단 함수들을 따로 코너를 두어 만들어보고자 한다.
간단한 로직을 구현하기위해서 사용하는 simple code이지만 모아두면 나중에 쓸모가 있을거 같아서 ㅎㅎㅎ

- 문자열의 순서 뒤집기 (좌우대칭) = String reverse
s = abcde
s = s[::-1]  # edcba

- 십진수를 이진수 문자열로 바꾸기
n = 5
n = bin(5)  # '0b101'

- 이진수 문자열을 십진수 숫자로 바꾸기
s = '101'
n = int(s, 2) # 이진수가 아닌 3진수였다면 2가아닌 3을 넣으면 됨.
print n         # 5

<Solution 1> built-in 함수 : Python - Accepted

================================================
실행시간 : 53ms
시간복잡도 : O(N)
공간복잡도 : O(1)
================================================

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        s = bin(n)[2:]
        l = 32-len(s)
        for i in range(l) :
            s = "0"+s
        return int(s[::-1],2)

<Solution 2> 비트연산 활용 : Python - Accepted

================================================
실행시간 : 62ms
시간복잡도 : O(N)
공간복잡도 : O(1)
================================================

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        result = 0
        for i in range(16) :
            msb = (n >> (31-i) ) & 1 # from right side bit
            lsb = (n >> i) & 1 # from left side bit
            result |= msb << i
            result |= lsb << (31-i)
        return result

핑백



통계 위젯 (블랙)

9221
1191
243252

GoogleAdsenseResponsive

Cluster map