[C] LeetCode 263. Ugly Number

 

 

문제(영어)

문제 번역

못생긴 숫자는 2,3,5 외에는 소인수가 없는 양의 정수이다. 정수 n이 주어졌을때 만약 못생긴 숫자면 true를 반환해라.

 

 

접근 방법

먼저 제약 조건을 보니 n은 4 byte integer 범위의 수인 것을 알 수 있다.

못생긴 숫자는 양수만 다루니 1보다 작은 모든 수는 false인 것을 알 수 있다.

 

그 다음 소인수 분해를 해야하는데, 2,3,5 숫자 3개로만 소인수 분해를 하면 된다.

만약 소인수 분해를 했는데 이 이외의 수를 소인수로 갖고 있다면 false를 반환 하고 아니면 true를 반환하면 된다.

 

먼저 입력받은 수 n을 2로 나눈 나머지가 0인동안(즉, 2로 나눠지는 동안) 2로 계속해서 나눈다.

그 다음 3으로 나눈 나머지가 0인동안(즉, 3으로 나눠지는 동안) 3으로 계속해서 나눈다.

마지막으로 5로 나눈 나머지가 0인동안 5로 계속해서 나눈다.

 

그래서 남은 수가 1이라면 이 수는 2,3,5의 소인수로만 구성된 수라는 것을 파악할 수 있다.

남은수가 1이 아니라면 이 수는 다른 소인수를 갖고 있는 것이다.

 

코드

bool isUgly(int n) {
    if(n < 1) return false;
    while(n % 2 == 0) n /= 2;
    while(n % 3 == 0) n /= 3;
    while(n % 5 == 0) n /= 5;
    if(n==1) return true;
    else return false;
}

 

시간/공간복잡도 분석

먼저 이 코드의 공간복잡도부터 보자. 추가적인 변수 선언이 없이 오직 int n만 필요하므로 O(1)이다.

시간복잡도의 경우 O(log n)이다.

2로 계속해서 나누므로 최대 나눌 수 있는 숫자는 log_2 (n)이다.

3으로 계속해서 나누기에 최대 log_3 (n)번 나눌 수 있다.

5 역시 마찬가지로 log_5 (n)이 최대이다.

 

따라서 시간복잡도는 O(log_2 (n) + log_3 (n) + log_5 (n)) = O(log n)  이다.