주어진 수가 4의 거듭제곱인지 확인하기

문제

주어진 정수가 4의 거듭제곱인지 확인하시오.

Given an integer, check if it is a power of 4.

입력

음수가 아닌 양의 정수

출력

4의 거듭제곱 수 일 경우

This num {input} is power of 4

4의 거듭제곱이 아닐 경우

This num {input} is not power of 4

실패한 풀이

처음에는 비트 연산자를 활용해 문자를 해결해 보려고 했다.
하지만, 문제를 모두 해결한 줄 알았을 때 예외 사항을 발견해 수정했다.

일단 처음에 해결하려고 했던 방법을 설명해보겠다.
입력값으로 주어진 수를 Python 내장 함수인 bin함수를 사용해
다음과 같이 2진수로 변경했다.

num = bin(num)[2:]

문자열 슬라이싱을 사용한 이유는 입력값이 16일 경우
bin함수를 사용해 나온 2진수는 0b10000과 같은 str타입이 되어
불필요한 부분인 앞의 0b부분을 제거하기 위해 잘라내었다.

그다음에 숫자 4의 2진수 값은 100이므로 2진수로 변환한
데이터의 길이가 3일 경우 2진수의 값이 100일 경우 4의 배수
2진수의 값이 100이 아닐 경우 4의 배수가 아닌 것으로 판단했다.

코드로 나타내자면 아래와 같다.

if len(num) <= 3:
        if num == '100':
            print("This num is 4's square")

        else:
            print("This num is not 4's square")

        break

여기에서 break를 사용한 이유는 길이가 3보다 작거나 같을 때까지
무한 루프안에서 비트 연산자를 사용해 4로 나누어 주었기 때문이다.

if문에 걸리는 elif문은 다음과 같다.

elif len(num) > 3:
    num = int(num, 2) >> 2

str타입의 데이터 값을 int함수에 argument로 2를 전달해
다시 2진수로 바꾸어 준후 2비트 시프트해 4로 나누어 주었다.

전체적인 코드는 아래와 같다.

while True:
    num = bin(num)[2:]

    if len(num) <= 3:
        if num == '100':
            print("This num is 4's square")

        else:
            print("This num is not 4's square")

        break

    elif len(num) > 3:
        num = int(num, 2) >> 2

몇 개의 입력값을 넣어보았을 때 문제없이 작동되는 듯 했으나.
예외를 찾게 되어 수정하게 되었다.
입력값이 17일 경우 2진수로 바꾸게 되면 10001이 된다.
길이 조건을 충족하지 못해 elif문에 들어가 시프트 연산을 하면
2진수값은 100이 되게 된다. 이 경우에는 입력값이 4의 제곱수가 아님에도
4의 거듭제곱 수가 맞다는 출력 결과를 도출하게 된다.

따라서 다른 방법으로 문제를 풀어보았다.

성공한 풀이

이번에는 좀 간단하게 접근해보았다.
주어진 숫자를 4로 나눈 나머지가 0이 아닐 경우에는
그 수는 무조건 4의 거듭제곱이 아닌 것을 판단할 수 있고
주어진 숫자가 1이 될 때 까지 조건을 판단하며 4로 나누어 주면 된다.

예시

입력값이 16일 경우 (4의 거듭제곱)

16은 1이 아니기 때문에 조건(4로 나누어지는 가)를 판단하게된다.
16은 4로 나누어지기 때문에 조건을 만족시키지 못하므로 계속 진행한다.
16을 4로 나누게 되면 num은 4가 된다.
이 바뀐 값 또한 조건을 충족시키지 못하므로 또 4로 나누어
이제 num값은 1이 된다.
num이 1이 되었기 때문에 반복문에서 탈출하게 되어 True를 반환한다.

입력값이 5일 경우 (4의 거듭제곱이 아님)

5는 1이 아니기 때문에 반복문을 진행한다.
숫자 5는 4로 나누어지지 않기 때문에 False를 반환한다.

코드 구현부

위의 풀이를 python코드로 함수를 구현하면 아래와 같다.
입력값이 0인지 판단한 후 0일 경우 False반환
그렇지 않을 경우 else구문을 진행한다.
주어진 숫자가 1이 되거나 4로 나누어지지 않을 때 까지 반복한다.
1이 되는 경우는 4의 거듭제곱인 경우이며
나누어지지 않을 때는 주어진 숫자가 4의 거듭제곱이 아닌 경우다.

def is_power_of_four(num):
    if num == 0:
        return False

    while num != 1:
        if num % 4 != 0:
            return False

        num = num // 4

    return True

num = int(input())

if is_power_of_four(num):
    print("This num {} is power of 4".format(num))

else:
    print("This num {} is not power of 4".format(num))

실행 결과