LeetCode 263(Ugly Number, Python)

1. 문제 링크

• Ugly Number - LeetCode

Ugly Number - LeetCode

2. 문제 설명

• 주어진 숫자가 Ugly Number인지 판별하는 문제
• Ugly Number란 오직 2, 3, 5 세 소수의 곱으로만 이루어진 양의 정수
• 예시) 6, 8은 True, 14는 False, 단 1은 Ugly Number임

3. 처음 풀이

• 2로 나눠지는 만큼 모두 나누고, 3, 5도 마찬가지로 모두 나누면 1이 되어야 ugly number이다. 

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

4. 다른 풀이

• 똑같은 풀이인데 while문을 3번 쓰는 것을 이렇게 간단히 쓸 수 있다.

class Solution:
    def isUgly(self, n: int) -> bool:
        if n==0:
            return 0
        for i in 2,3,5:
            while n%i==0:
                n//=i
        return n==1

 

---

• 분자에 2, 3, 5를 충분히 많이 곱하고, 주어진 수를 분모에 넣어 나누었을 때, 2, 3, 5가 아닌 소인수가 있다면 자연수가 아닌 유리수가 됨을 이용한다.

class Solution:
    def isUgly(self, n: int) -> bool:
        if n<1:
            return False
        multiple=2*3*5
        return (multiple**20)%n==0

5. 배운 점

• for 문 안에 while문을 넣을 수 있다.
• 소수 p를 약수로 갖지 않는 수를 p를 약수로 갖는 수로 나누면 정수가 되지 않는다. 이를 이용하면 편할 수 있다.