[Codility] CountNonDivisible 풀이 정리 (Java)

source 는 Github 에 있습니다.

문제

• 문제

풀이

첫번째 풀이

• 문제 풀이의 concept 을 array element 끼리 나눌 수 없는지 확인하도록 했습니다.
  • int[] A = new int[] {3,1,2,3,6}; 라면 3/1, 3/2, ... 이런식으로 concept 을 잡았습니다.
• array element 끼리 나누면서 발생하는 중복 계산은 cache 로 저장해서 중복 계산을 피했습니다.
• 시간복잡도는 O(n제곱) 이였고, 실행해본 결과 정확도 100%, performance 0%

두번째 풀이

• 문제 풀이의 concept 은 다음과 같습니다.
• array 에서 발생하는 숫자 빈도수를 계산해서 메모리에 저장합니다.
• array 를 순회하면서 1부터 element 까지 약분하도록 했습니다.
  • 이 때, 주의할점이 1부터 element 까지 모두 순회하는게 아니라 제곱근이 A[i] 크거나 작을 때까지만 순회합니다.
  • 자세한 설명은 소스 주석에 달아놨습니다.
• 이렇게 순회하면서 A[i] 의 약수를 구하고, 그것을 A.length - 약수 로 result 를 구했습니다.
• 시간복잡도는 O(n * logn) 이며, 공간복잡도는 O(n) 입니다.

source

    public int[] solution(int[] A) {
        int[] result = new int[A.length];

        // divisors 는 숫자 빈도를 저장하는 것
        int[] divisors = new int[(A.length * 2) + 1];
        for (int i = 0 ; i < A.length ; i++) {
            divisors[A[i]]++;
        }


        // A 를 순회한다.
        for (int i = 0 ; i < A.length ; i++) {
            int count = 0;

            // 이게 핵심 concept. 1부터 A[i] 까지 나누어주는데. 제곱근까지만 구함.
            // 왜냐하면 앞에꺼를 구하면 뒤에꺼를 또 구할 필요가 없음.
            // 예를 들면, 8 의 약수를 구하는 것이라면 1,2,4,8 이며, 앞의 1,2 만 구하면 뒤에 4,8을 구할 수 있기에 뒤에꺼 계산할 필요가 없음.
            // 16의 경우 1,2,4,8,16 이며, 앞의 1,2,4 까지는 구해야 약수를 구할 수 있음. 즉, 여기서 시간복잡도가 반씩 줄어드는 것.
            for (int j = 1 ; j * j <= A[i] ; j++) {
                // 약수를 구함. 위 예시대로라면 1,2 를 구하는 것임.
                // 구한 뒤에, 미리 구한 divisors 를 더해주는 것이다.
                if (A[i] % j == 0) {
                    count += divisors[j];

                    // 위에서 4,8 을 추가로 구하는 계산 방식임. 만약 제곱근이면 위에서 이미 한 번 구했으니 +1 을 안해도 되지만,
                    // 제곱근이 아니면 약수는 2개이기 때문
                    if (A[i] / j != j) {
                       count += divisors[A[i]/j];
                    }
                }
            }
            result[i] = A.length - count;
        }
        return result;
    }