[LeetCode] 1780. Check if Number is a Sum of Powers of Three (Python)

 

 

난이도: Medium

Problem Description

---

 

Given an integer n, return true if it is possible to represent n as the sum of distinct powers of three. Otherwise, return false.

 

An integer y is a power of three if there exists an integer x such that y == 3x.

 

Problem Example

---

Example 1:

Input: n = 12
Output: true
Explanation: 12 = 3^1 + 3^2

Example 2:

Input: n = 91
Output: true
Explanation: 91 = 3^0 + 3^2 + 3^4

Example 3:

Input: n = 21
Output: false

 

Constraints

---

• 1 <= n <= 107

 

✏️ Solution

---

class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        check_sum = []

        for i in range(16):
            three_power = 3 ** i

            if three_power < n:
                check_sum.append(three_power)
                
                for j in range(len(check_sum)-1):
                    sum_power_of_three = check_sum[j] + three_power

                    if sum_power_of_three == n:
                        return True

                    elif sum_power_of_three < n:
                        check_sum.append(sum_power_of_three)
            
            else:
                return three_power == n

 

먼저 3의 15승까지의 값을 for문을 통해서 구하고, check_sum 리스트에 이를 저장했다.

 

이때 3의 i승이 n보다 작다고한다면, 앞서 구했던 값들과 모두 더해보고 그 중 한 값이 n과 같다면 True를 반환했다.

만약 값이 작다면 check_sum에 더한 값을 저장했다.

 

예를 들어, n이 12라고 한다면 check_sum에는 각 반복마다 다음과 같이 저장된다.

• i = 0  --> 3^0 =1, check_sum = [1],  1은 12보다 작긴 하지만 앞선 값이 없기 때문에 다음으로 넘어감
• i = 1 --> 3^1=3, check_sum =[1,3],  3은 12보다 작으니까 앞선 값을 더해준 값을 check_sum에 추가 --> check_sum = [1, 3, 4]
• i = 2 --> 3^2=9, check_sum =[1,3,4,9], 9는 12보다 작으니까 앞선 값을 모두 더해준 값들을 check_sum에 추가 --> 1 + 9 =10, 3+9 =12, 4+9 = 13 이때, 3+9 = 12로 n과 같기 때문에 True 반환

 

만약 3의 i승이 n보다 작지 않다면 3의 i승 과 n이 같은 지 확인한 bool 값을 정답으로 return 하였다.

 

---

 

다른 사람들의 풀이를 보니 이 문제는 삼진법을 이용하면 쉽게 풀 수 있는 문제였다..

 

n을 삼진법으로 표현했을 때, 2가 있으면 False 1과 0만 있으면 True를 반환하면 문제 조건을 만족한다.

 

왜냐하면 삼진법에서 2가 있다는 것은 그 위치에 해당하는 3^k 항이 두번 더해졌다는 의미이기 때문이다.

하지만, 문제의 조건은 3^k를 한 번씩만 사용할 수 있는 경우를 판별하는 문제로 볼 수 있다.

 

즉 n을 삼진법으로 표현했을 때, 2가 없으면 3의 거듭제곱들의 조합으로 표현 가능하다고 볼 수 있다.

 

이를 코드로 작성하면 다음과 같다.

class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        while n!=0:
            if n % 3 == 2:
                return False
            n //= 3
        
        return True

 

⚙️ Runtime & Memory

---

위 코드

 

아래 코드

 

 

---

문제: 1780. Check if Number is a Sum of Powers of Three

 

깃허브: github

algorithmPractice/LeetCode/1889-check-if-number-is-a-sum-of-powers-of-three at main · laewonJeong/algorithmPractice