LeetCode 231(Power of Two, Python)

1. 문제 링크

• https://leetcode.com/problems/power-of-two/description/

2. 문제 설명

• 정수 n이 주어졌을 때, 만약 해당 수가 2의 거듭제곱이면 True를 아니면 False를 반환
• 예시1) n=1일 때, 1은 2의 0 거듭제곱이므로 True 반환
• 예시2) n=16일 때, 16은 2의 4 거듭제곱이므로 True 반환 
• 예시3) n=3일 때, 3은 2의 거듭제곱이 아니므로 False를 반환

3.  처음 풀이

• Follow up에서 loops나 recursion을 쓰지 않고, 풀 수 있는지를 물어봐서 다른 방법을 생각해보다가,
• 10진법을 2진법으로 바꾸었을 때, 2의 거듭제곱이라면 
  • 10000, 100, 10 등의 형태일 것이기 때문에, 
  • 1을 제외한 값을 int로 변환했을 때, 해당 값이 0이면 True를, 아니면 False를 반환하도록 작성
  • bin(10)을 하면 '0b1010'과  같이, 앞에는 0b라는 문자열이 붙기 때문에, bin(2)[3:]으로 판단하고,
    
    • 0이나 1의 경우 bin(2)[3:]이 비어있기 때문에 예외처리를 해두었다.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if bin(n)[3:] == '': 
            return bin(n)[2:] == '1'
        return int(bin(n)[3:]) == 0

 

4. 다른 풀이

• easy문제여서 풀이가 간단한데, 꽤 다양하게 있었다.
• 아래는 bit_count()라는 함수를 활용한 풀이. 여기서 bit_count()는 정수의 이진표현에서 1의 개수를 세는 것. 
  • 그래서 나처럼 직접 bin(n)으로 이진법으로 변환할 필요없이,
  • n.bit_count() == 1인지 check하는 것도 가능하다. 

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n.bit_count() == 1 and n > 0

• 아래는 그냥 for문을 돌리면서, 2**i했을 때, 해당 값이 나오면 True, 나오지 않으면 False를 반환

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        for i in range(n - n // 2 + 1):
            if 2 ** i == n:
                return True
            if 2 ** i > n:
                return False

• 비트 연산자를 활용한 풀이 (해당 풀이가 정석적인 풀이같다.)
  • n과 n-1을 and 연산.
    • n이 2의 거듭제곱이라면 항상 하나의 비트만 1로 설정된 이진수이고, n-1은 해당 비트를 0으로 만들고, 그 아래비트를 모두 1로 설정하게 되므로, n & n-1의 결과는 항상 0이 된다.
    • 이에 여기에 not 연산자를 이용하면, True이면 주어진 수가 2의 거듭제곱이 되는 것 

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        
        return n > 0 and not (n & n-1)