https://app.codility.com/programmers/lessons/5-prefix_sums/count_div/
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.
A부터 B까지 K로 나누었을 때 0이 되는 숫자들을 세는 문제입니다.
브루트포스로 생각하면 당연히 A부터 B까지 숫자를 1씩 증가시키면서 K로 나누었을 때 0이되는 수를 세면 됩니다.
하지만 당연히 오랜 시간이 걸리며 테스트 결과도 타임 아웃이 날 것입니다.
실제로 테스트 해봤을때 정확도는 만점이지만 속도와 효율에서 0점을 기록하여 전체 점수 50점에 그치고 말았습니다.
그렇다면 어떻게 해야할까요?
제가 처음에 생각한 방법은 A부터 B까지 K의 배수의 갯수를 세는 것이었습니다.
즉 A가 6부터 B가 11까지 K의 배수의 개수는 6, 8, 10 총 3개입니다.
하지만 이 방법도 결국 K의 배수 만큼 루프를 돌면서 카운팅을 해야 하기 때문에 그다지 좋은 효율이 아닐거라 생각했습니다.
천천히 고민하다보니 좋은 방법이 떠 올랐는데요.
배수의 갯수를 센다는 것은, 나누는 것과 마찬가지 입니다. 즉 1부터 10까지 2의 배수는 총 5개인데요.
2씩 배수로 카운팅을 하는것과 10 / 2 = 5 인 것과 동일한 것이겠죠. 단순한 원리이지만 코딩 테스트를 하면서 단순하게 생각하는 것도 어려운 일인거 같습니다.
쨌든 우리는 나누기를 통해 카운팅이 가능한 것을 알았습니다. 그렇다면 마무리는 어떻게 하면 될까요?
우리는 A부터 B까지의 배수를 세야 합니다. 그러니, 1부터 B까지의 배수를 모두 구하고 1부터 A까지의 배수의 개수를 빼면 A부터 B까지의 배수를 구할 수 있습니다.
추가로 A가 K의 배수인 경우에도 카운팅을 해줘야 할텐데요.
때문에 마지막에 나머지가 0일 경우 1을 더해주는 로직을 추가하였습니다. 결과는 Total score 100%과 O(1)의 결과를 얻었네요.
https://github.com/lkimilhol/studyForCodingTest/blob/master/src/com/company/codility/CountDiv.java
public class CountDiv {
public static int solution(int A, int B, int K) {
int first = A / K ;
int second = B / K;
int third = A % K == 0 ? 1 : 0;
return second - first + third;
}
}