263. Ugly Number

https://leetcode.com/problems/ugly-number/

Ugly Number - LeetCode

해당 문제는 2,3,5로 나누어지는 수를 구하는 문제입니다.

소수 판정하는 방법과 유사하지만 17 의 경우 소수이지만 2, 3, 5 나누어 떨어지지 않기 때문에 ugly number 입니다.

수		판정
3	3 -> 1	X
20	20 -> 10 -> 5 -> 1	X
6	6 -> 3 -> 1	X
4	4 -> 2 -> 1	X
5	5 -> 1	X
17	2/3/5 중 나누어 지는 수가 없음	X

D 풀이

class Solution {
public:
    bool isUgly(int num) {
        
        bool find = false;
        while (num > 0) {

            int div2 = num % 2;
            int div3 = num % 3;
            int div5 = num % 5;
            if (div2 == 0) {
                num = num / 2;
            }

            if (div3 == 0) {
                num = num / 3;
            }

            if (div5 == 0) {
                num = num / 5;
            }

            if (num == 1) {
                find = true;
                break;
            }
            
            
            if (div2 && div3 && div5) {
                find = false;
                break;
            }
        }

        return find;
    }
};

 

O 풀이

while문을 2,3,5 따로 처리하는 프로세스가 불필요한 연산 줄임.

class Solution {
public:
    bool isUgly(int num) {
        
        int temp;
        do
        {
            temp = num;
            if( num % 2 == 0 )
                num = num / 2;
            if( num % 3 == 0 )
                num = num / 3;
            if( num % 5 == 0 )
                num = num / 5;
                   
            if( num == 1 )
                return true;
            
        }while(temp != num);
        
        
        return false;
    }
};

 

W 풀이

class Solution {
public:
    bool isUgly(int num) {
        if (num <= 0)
            return false;
        
        while (num%2 == 0)
            num /= 2;
        
        while (num%3 == 0)
            num /= 3;
        
        while (num%5 == 0)
            num /= 5;
        
        return num == 1;
    }
};