231. Power of Two

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

불러오는 중입니다...

 

와 이거 정말 환장하겠네 엄청 쉽다고 생각한 문제였는데 8번 연속 틀려서 막일로 접근해서 풀었음.

일단 2의 제곱인지 확인하는 문제임.

 

 

완전 노가다 접근

0 이면 제곱 아니면

1, 2 는 제곱수

그 외에의 2의 제곱인지 판단하기 위해서 테이블을 만듦 INT 자료 범위 맥스까지 2 곱해서 TABLE을 만든다.

모든 2의 제곱을 TABLE에 계산해서 기록한다.

이후 기록한 테이블과 입력으로 들어오는 N의 값이 같으면 TRUE 

N의 값이 TABLE에 값 보다 크다면 FALSE로 막일로 풀었다. 으아아 아..

 

class Solution {
public:
    bool isPowerOfTwo(int n) {
        
        if(n == 0)
            return false;
        
        if(n == 1)
            return true;
        
        if(n == 2)
            return true;
        
        long long cand = 2;
        int int_max = 2147483647;
        vector<int> arr;
        int table_max = sqrt(int_max);
        
        for(int i=0; i<table_max; i++) {
            cand *= 2;
            if(cand > int_max) {
                break;
            }
            arr.push_back(cand);
        }
        
        for(int i=0; i<arr.size(); i++) {
            int cand = arr[i];
            if(cand > n) {
                return false;
            }
            
            if(arr[i] == n) {
                return true;
            }
        }
        
        return false;
    }
};

 

아무리 생각해도 멍청한 짓 같아 2의 거듭제곱인지 판단하는 글을 보고 적용했는데.. 안된다.

https://sgc109.tistory.com/130

2의 거듭제곱인지 O(1)에 판별하는 방법

저 필자의 블로그 내용이 틀린 건 아닐 것이다. 해당 문제에서 자료 범위가 무엇인가 다른 게 있어서 그런 거 같다. 

 

문제의 원인을 찾았다. 입력으로 들어오는 N의 값이 음수도 들어올 수 있었다. 음수인 경우는 2의 배수가 아님으로 아래와 같이 에러 처리를 추가한다.

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n <= 0)
            return false;
        return (n & (n - 1)) == 0;
    }
};

비트 연산을 이용하여 마지막 비트가 없으면 2의 배수이다.