[ 알고리즘 ] LeetCode 869. Reordered Power of 2

이주 weekwith.me·2022년 8월 26일

목록 보기

71/73

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 869. Reordered Power of 2를 풀고 작성한 글입니다.

문제

요구사항

You are given an integer n . We reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this so that the resulting number is a power of two.

제약사항

1 <= n <= 10^9

풀이

접근법

총 두 가지 풀이가 존재한다.

범위를 한정한 뒤 정렬을 활용한 풀이
비트 연산자를 활용한 풀이

첫 번째 풀이

아래와 같이 내장 모듈 math 내에 있는 log() 함수를 활용하여 반복문의 범위를 한정하고 해당 범위 내로 반복문을 수행하며 sorted() 내장 함수를 통해 두 수를 비교해서 2의 제곱수로 만들 수 있는지 여부를 판별한다.

def solution(n: int) -> bool:
    from math import log
    
    
    length: int = len(str(n))
    start: int = int(log(10 ** (length - 1), 2))
    end: int = int(log(10 ** length, 2))
    
    for number in range(start, end + 1):
        if sorted(str(n)) == sorted(str(2 ** number)):
            return True
    
    return False

두 번째 풀이

비트 연산자를 활용해서 문제를 풀 수도 있다.

최대 9자리까지인 입력값에 따라 2의 배수 또한 최대 2^30까지만 따지면 되기 때문에 2^0부터 하나씩 비트 연산을 통해서 비교하면 된다.

이때 해당 수의 개수를 따져 비교하면 순서에 상관 없이 비교할 수 있다.

def solution(n: int) -> bool:
    numbers: dict[str, int] = {}
    for number in str(n):
        if number in numbers:
            numbers[number] += 1

        else:
            numbers[number] = 1


    for power in range(30):
        target: int = 1 << power
        target_numbers: dict[str, int] = {}
        for number in str(target):
            if number in target_numbers:
                target_numbers[number] += 1

            else:
                target_numbers[number] = 1

        if numbers == target_numbers:
            return True


    return False