Codility Lesson 10 - CountFactors(JAVA)

https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/count_factors/

CountFactors coding task - Learn to Code - Codility

 

문제

- 양수 D는 N의 factor이다.

- factor인 것은 N = D * M이 성립될 때를 의미한다.

- 예시 : N = 24일 때 factor는 1,2,3,4,6,8,12,24 총 8개를 의미한다. return 8

 

제한조건

• N is an integer within the range [1..2,147,483,647].

N은 1 ~ 2,147,483,647 사이의 정수이다.

 

풀이

- count = 0으로 초기화 한다.

- for문을 1 ~ N만큼 순회시키며 인덱스로 나눠지는지를 확인한다.

- for문을 순회하며 해당하는 인덱스로 나누어지는 경우 count+2를 한다.( 반대의 경우엔 continue )

- 모든 for문을 순회할 필요 없이 factor인 것과 쌍이 되는( 여기서는 나눴을 때의 몫 )을 mok 변수에 저장하며 인덱스의 값이 몫과 같아지는 경우에 종료한다.

- 예시에서 (1,24) -> mok = 24, (2,12) -> mok = 12, ... (4,6) -> mok = 6 ... index = 6이 되면 mok과 같아지기에 이 부분에서 break후 return count

 

예상 시간복잡도 : O(N)보다는 작은 시간복잡도 예상( for문을 전부 순회하지는 않을 것! )

 

소스코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int N) {
        // write your code in Java SE 8
        // N이 1일 경우 for문이 동작하지 않고, N까지 고려해야하는 것을 가정하여 증감식에는 N+1로
        int count = 0;
        int mok = 0;
        for( int i=1; i<N+1; i++ ){
            if( i == mok ) break;

            if( N % i == 0 ){    
                mok = N / i;
                count += 2;
                // System.out.println("i : " + i);
                // System.out.println("mok : " + mok);
            }
        }

        return count;
    }
}

 

문제를 제대로 이해하지 못한 모양이다..

Integer 범위만큼 for문을 돌리는 것 자체가 문제이고, 무조건 양수의 쌍이 나오는 것은 아닌가봄..

명일 제대로 이해하고 재풀이 하기!

 

4/8일 재풀이

- for문을 1부터 N까지 순회하게 했을 경우 최악의 경우 Integer범위만큼 모두 도는 것은 timeout이 나올 것..

- 소인수분해를 활용하여 약수의 개수를 구하는 방식으로 풀이

- 예시인 24 = 2^3 * 3^1로 제곱수를 활용하여 약수의 개수를 구할 수 있음

- 약수의 개수는 각 (2의 제곱수+1) * (3의 제곱수+1)

- 예외로는 소수인 수들( 7, 11, 13 ... )은 1과 자기자신만을 약수로 가진다.

- 소수와 2,3,5인 소인수들과 곱해진 경우의 수도 존재한다.

- 위의 경우들을 바탕으로 문제를 풀이한다.

 

풀이

- 소인수는 3가지( 2, 3, 5 )만 존재하며 N으로 주어진 수들을 소인수분해 한다.

- 소인수 분해를 하며 각 제곱수들을 카운트한다.

- 소인수분해를 통해 얻은 제곱수로 약수를 구하는 공식을 활용한다.

 

소스코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int N) {
        // write your code in Java SE 8

        // 소인수 분해를 의미하는듯?
        // 12 = 1,2,3,4,6,12 -? 2^2 * 3^1 -> (2 + 1) * (1 + 1) = 6
        // 17 = 1, 17 -> 2

        if( N == 1 ) return 1;

        int answer = 0;

        int two_count = 0;
        int three_count = 0;
        int five_count = 0;

        int tmp = N;
        while( tmp % 5 == 0 ){
            five_count += 1;
            tmp = tmp / 5;
        }

        while( tmp % 3 == 0 ){
            three_count += 1;
            tmp = tmp / 3;
        }

        while( tmp % 2 == 0 ){
            two_count += 1;
            tmp = tmp / 2;
        }

        if( tmp == 1 ){
            // 모두 나누어 떨어진 경우( 소수가 존재 하지 않는 경우 )
            answer = (two_count + 1) * (three_count + 1) * (five_count + 1);
        }else{
            answer = (two_count + 1) * (three_count + 1) * (five_count + 1) * 2;
        }
        
        return answer;
    }
}

 

결과

timeout은 나오지 않지만 잘못된 결과들이 나온다.( 소수와 소수의 곱으로 이루어진 수들이 존재함 )

 

결국 구글링..

이분의 블로그를 참고하여 풀어본다

https://deefer.tistory.com/122?category=826956 

Lesson10 - CountFactors

 

소스코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int N) {
        // write your code in Java SE 8
        int answer = 0;

        double sqrt = Math.sqrt(N);
        int sqrt_int = (int)sqrt;

        if( sqrt_int == sqrt ) answer -= 1;

        // System.out.println("sqrt : " + sqrt + " / sqrt_int : " + sqrt_int);
        
        for( int i=1; i<sqrt_int+1; i++ ) {
            if( N % i == 0 ){
                answer += 2;
            }
        }

        return answer;
    }
}

 

 

수학적인 지식이 어느정도 필요하다..

주의할 점

- sqrt시 제곱수가 되는 25, 36 등의 수들은 약수가 1개가 됨으로 고려해야한다.

- 제곱근을 구해서 그 수만큼만 for문을 순회하며 N의 약수가 되는 경우를 구하면된다( 대칭인 점을 이용 )

 

easy지만 나에게는 easy하지 않았던 문제..ㅠ