[Python] leetcode-869.Reordered Power of 2

hannah·2024년 6월 30일

algorithm

목록 보기

7/11

문제 설명

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

입출력 예제

n	return
1	True
10	False

처음에는 주어진 n을 스트링으로 형변환 후 그걸 정렬하고 해당 리스트를 기반으로 나올 수 있는 모든 경우의 수를 lst라는 리스트에 넣은 뒤, 맨 앞자리가 0인 경우를 뺀 나머지 경우에 중복을 제거하여 temp_list에 넣어주었다.
그 후, 원소를 하나씩 확인하며 수가 2의 거듭제곱이면 바로 True를 반환하고 아닐 경우에는 다음 수로 넘어가서 확인하다가 결국 거듭제곱이 없으면 False를 반환하는 방식으로 구상했다.

코드 작성

첫번째 코드

from itertools import permutations

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        lst=list(permutations(sorted(list(str(n)))))
        temp_list=[]
        for i in range(len(lst)):
            if int(''.join(lst[i])) not in temp_list:
                if lst[i][0]=='0':
                    continue
                temp_list.append(int(''.join(lst[i])))
        result=False
        for num in temp_list:
            while num:
                if num==1:
                    return True
                elif num%2==0:
                    num//=2
                    result=True
                else:
                    result=False
                    break
        return result

결과

실패,,원인은 시간초과였다...시간을 어떻게 하면 줄일 수 있을까 골똘히 고민하면서 2의 거듭제곱을 확인하는 과정에서 연산을 줄이기 위해 코드를 고쳐 두번째 시도를 해보았다..

두번째 코드

### 첫번째 코드
```py
from itertools import permutations

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        lst=list(permutations(sorted(list(str(n)))))
        temp_list=[]
        for i in range(len(lst)):
            if int(''.join(lst[i])) not in temp_list:
                if lst[i][0]=='0':
                    continue
                temp_list.append(int(''.join(lst[i])))
        result=False
        for num in temp_list:
            while num:
                if num==1:
                    return True
                elif num%2==0:
                    num//=2
                    result=True
                else:
                    result=False
                    break
        return result

결과

유의미한 시간단축은 없는건지 같은 테케에서 시간초과 에러가 떴다..흐으음 아예 다른 방식으로 접근해야 하는건가 고민을 했다. 그러다가 숫자로 변환해서 그걸 중복없이 리스트에 담아서 2의 거듭제곱인지 확인하는 것이 아닌 스트링으로 둔 채로 2의 거듭제곱과 일치하는지 확인하는 방법을 생각했다..

세번째 코드

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        n=sorted(str(n))
        for i in range(30):
            curr_power=sorted(str(2**i))
            if n == curr_power:
                return True
        return False