Codility_CountDiv

5-2. CountDiv

Write a function:

class Solution { public int solution(int A, int B, int K); }

that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.:

{ i : A ≤ i ≤ B, i mod K = 0 }

For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.

Write an efficient algorithm for the following assumptions:

A and B are integers within the range [0..2,000,000,000];
K is an integer within the range [1..2,000,000,000];
A ≤ B.

세 개의 정수 A, B, K가 주어졌을 때, 범위 [A…B] 내에서 K로 나누어 떨어지는 정수의 개수를 반환하는 함수입니다. 즉:
{i:A≤i≤B,imodK=0}
예를 들어, A = 6, B = 11, K = 2일 때, 함수는 3을 반환해야 합니다. 왜냐하면 6에서 11 사이에 2로 나누어 떨어지는 숫자는 6, 8, 10 이렇게 세 개이기 때문입니다.
다음 가정에 대한 효율적인 알고리즘을 작성하세요:

A와 B는 [0…2,000,000,000] 범위 내의 정수입니다.
K는 [1…2,000,000,000] 범위 내의 정수입니다.
A ≤ B입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int A, int B, int K) {
        int div[] = new int[B - A + 1];
        int c = 0;
        for(int i = A; i <= B; i++) {
            div[c] = i;
            c++;
        }
        
        int count = 0;
        for(int r = 0; r < div.length; r++) {
            if(div[r] % K == 0) {
                count++;
            }
        }

        return count;
    }
}

배열은 만들어서 A와 B 사이의 정수들을 저장하고
해당 정수들을 나눴을 경우 나머지값이 0일 경우를 카운트하여 리턴해주었다.

제출결과

50%의 점수가 나온다;;;

주어진 값이 클 경우 메모리 사용량이 많아 RUNTIME ERROR가 발생하는 듯 하다.

수정코드

import java.util.*;

class Solution {
    public int solution(int A, int B, int K) {
        // A와 B의 범위를 확인하여 잘못된 입력을 방지합니다.
        if (A > B) {
            return 0;
        }

        // 배열을 사용하지 않고 효율적으로 계산합니다.
        int count = (B / K) - (A / K);
        if (A % K == 0) {
            count++;
        }
        return count;
    }
}

수학공식 : "B / K는 1부터 B까지의 숫자 중 K로 나누어 떨어지는 숫자의 개수를 나타냅니다. 마찬가지로, A / K는 1부터 A까지의 숫자 중 K로 나누어 떨어지는 숫자의 개수를 나타냅니다."
해당 공식으로 나눠지는 수를 구하고 A가 K로 나누어 떨어지는 경우를 추가해줍니다.(1부터 A까지의 나눠지는 수를 뺏음으로 A에 해당하는 것 만 다시 더해줌)

제출결과

문제풀어보기-> https://app.codility.com/programmers/lessons/5-prefix_sums/count_div/