[LeetCode] 869 Reordered Power of 2

🧩 Algorithm/LeetCode

[LeetCode] 869 Reordered Power of 2

nerowiki 2024. 6. 21. 23:49

728x90

💡 오늘의 학습 키워드

📌 문자열

문제 설명

문제 링크 : https://leetcode.com/problems/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. 1 <= n <= 10^9

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

n 값의 범위가 최대 10억인 점을 고려하여 효율적인 풀이 방식을 고민해야 하는 문제였습니다.
가장 직관적인 해결 방법으로 순열을 사용한 문제 해결 과정은 다음과 같습니다.

주어진 정수 n 값을 여러 조합을 고려할 수 있도록 string 타입으로 변환합니다.
해당 리스트를 순열을 통해 순회하면서 각 순열 값이 2의 거듭제곱인지 아닌지 비교합니다.
2의 거듭 제곱이 존재한다면 True 아니라면 False를 반환합니다.

해결 방법에서 모든 경우의 수를 고려한다는 점이 시간 복잡도에서 효율적이지 못한다는 것을 알 수 있습니다.
여기서 2진수의 비트 연산을 활용한다면 반복을 줄일 수 있다는 것을 발견할 수 있습니다.
순열을 통해 나온 값이 만일 2의 거듭제곱 값이라면 해당 값보다 1이 작은 값과 & 연산을 통해 0이 되는 것을 알 수 있습니다.

예를 들어 순열 값이 8이 나온다면 이를 이진수로 표현하게 되면 '1000' 값이 나오게 됩니다.
8보다 1 작은 수 7을 이진수로 표현하게 되면 '0111' 값이 나오게 되는데 이렇게 나온 값들을 & 연산해주게 되면
'0000' 으로 0이 나오게 되는 것을 이용한 것입니다.
이 방법을 사용하면 순열로 나온 값을 2의 거듭제곱인지 확인하기 위한 반복문 과정을 생략할 수 있게 됩니다.
따라서 이전 방법의 속도보다 약 절반정도 시간이 빨라진 것을 확인할 수 있습니다.

하지만 조금 더 생각해보면 비트연산과 정렬만으로 순열도 사용하지 않고 최단시간 내 풀이하는 방법을 찾을 수 있습니다.
n의 범위가 10억이라는 점을 고려해 해당 범위 내의 모든 2의 거듭제곱을 리스트에 저장하여 n 값과 비교하는 것입니다.

2의 30승이 되면 약 10억이 되므로 비트 연산을 통해 해당 거듭제곱 값들을 리스트에 저장합니다.
해당 거듭제곱 값들을 n값과 비교하기 쉽도록 sorted 정렬해줍니다.
n 값도 동일하게 sorted 정렬해줍니다.
이제 만일 n 값이 해당 거듭제곱 리스트 안에 존재하는지 검색한 후 이에 맞는 값을 반환합니다.

거듭제곱 값을 직접적으로 리스트에 저장하고 비교하는 방식으로 n 값을 탐색하는 과정을 생략할 수 있었습니다.
이 방식의 탐색 속도가 40ms인 점을 미뤄보아 위 방식들 중 가장 효율적인 방식인 것을 확인할 수 있습니다.

💡 내가 해결한 방식은?

순열과 반복문을 이용한 풀이 (2433 ms)

from itertools import permutations

def is_power_of_two(n):
    if n <= 0:
        return False
    while n % 2 == 0:
        n /= 2
    return n == 1

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        digits = list(str(n))
        for perm in itertools.permutations(digits):
            if perm[0] != '0':  # 앞자리가 0이 아닌지 확인
                num = int(''.join(perm))
                if is_power_of_two(num):
                    return True
        return False

순열과 비트 연산을 이용한 풀이 (1366 ms)

from itertools import permutations

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        str_n = list(''.join(str(n)))

        for each in permutations(str_n):
            if each[0] == '0':
                continue
            each = int(''.join(each))
            if each > 0 and (each & (each - 1)) == 0:
                return True
        
        return False

비트 연산과 정렬을 이용한 풀이 (40 ms)

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        p_of_2s = [str(1 << i) for i in range(31)]
        sorted_pOf2 = [''.join(sorted(p)) for p in p_of_2s]

        sorted_n = ''.join(sorted(str(n)))

        return sorted_n in sorted_pOf2

✍️ TIL

문제 풀이에 가장 직관적인 풀이 방법은 순열을 사용하는 것인데 이러한 직관적인 풀이도 제한 사항의 크기를 잘 고려해야 한다.
크기가 억 단위를 넘긴다면 직관적인 풀이에 한계가 있다는 것이므로 새로운 알고리즘을 활용하거나 풀이 아이디어가 필요한 것이다.
2의 거듭제곱은 2**n으로 표현할 수도 있지만 1 << i 로도 표현할 수 있다는 것, 2의 거듭제곱이라면 i & i-1 == 0 임을 알 수 있었다.
permutation으로 해당 n값의 다양한 조합을 따져야 한다고 생각했는데 2의 거듭제곱 값들을 미리 저장하게 된다면
n 값 조합할 필요 없이 단순 내림차순 정렬 비교로 풀이할 수 있었다.