[Codility] CountDiv

이번에 풀어볼 문제는 Codility lessons 5(Prefix Sums)에 있는 CountDiv 문제이다.

(https://app.codility.com/programmers/lessons/5-prefix_sums/count_div/)

 

---

[ 문제 ]

[a ... b] 사이 숫자들 중에 k로 나누어 떨어지는 숫자의 개수를 계산하시오.

 

---

[ 조건 ]

• 3개의 수가 주어진다. (A, B, K)
• A, B는 정수이며 [0 .... 2,000,000,000] 내에 존재한다.
• K는 정수이며 [1 .... 2,000,000,000] 내에 존재한다.
• A ≤ B

 

---

[ 접근방법 ]

 

직관적으로 생각하기

 

주어진 범위 내 정수들을 순회하면서 나누어지는지, 나누어지지 않는 지를 모두 검사하는 방법이다. 이 방법이 무조건 안 좋은 방법은 아니지만 조건들을 보면 정수의 범위가 2,000,000,000로 큰 숫자임을 고려했을 때 그렇게 좋은 방법은 아니다.

 

조금 더 나아가 보기

 

범위 내 숫자들 중에 K의 배수가 몇 개인지에 대한 질문으로 바꿔서 생각해 보면 배수의 문제로 바뀌게 된다. 예전 배수를 배우던 시절로 잠시 돌아가 보면 1부터 100까지 숫자 중에 3의 배수는 어떻게 구하게 될까? 3, 6, 9, 12, 15, 18 ..... 이렇게 100까지 구하면 구할 수 있다. 이것을 아래 식처럼 정리해 보면, 

 

3, 6, 9, 12, 15, 18, ..... , 99 = 3 × 1, 3 × 2, 3 × 3, 3 × 4, 3 × 5, 3 × 6 .... , 3 × 33

 

이제 1부터 100까지 3의 배수가 몇 개인지 알 수 있다. 33개이다. 

 

이제 문제에 적용하기 위한 고려사항이다.

 

• 0부터 시작했을 때를 고려해야 한다. (0 은 어떤수로 나누어도 나누어진다.)
  [0, 1, 2, 3, 4, 5, 6, 7, 8] 이며, K = 3 인 경우,
  3의 배수의 개수: 8 / 3 = 2 (0 을 고려하지 않은 경우)
  0은 모든 수의 배수 (어떤 수로 나누어도 떨어진다)이므로 0이 있는 경우 +1 
  ∴ 최종 3의 배수의 개수: 2 + 1 = 3
  
• 0이 아닌 숫자부터 시작했을 때 배수의 개수와 주어진 숫자의 시작점 이전까지 존재하는 배수의 개수를 빼줘야 한다.
  [5, 6, 7, 8] 이며, K = 3 인 경우,
  전체 3의 배수의 개수 - [0, 1, 2, 3, 4] 내 3의 배수의 개수 = 3 - 2 = 1
  ∴ [5, 6, 7, 8] 내에 존재하는 3의 배수의 개수 = 1
  

 

---

[ 코드 구현 ]

 

public class CountDiv {
    public int solution(int A, int B, int K) {
        int tc = B / K;
        int pc = (A - 1) / K;
        if (A == 0) {
            return tc + 1;
        } else {
            return tc - pc;
        }
    }
}

 

---

[ References ]

• https://m.blog.naver.com/ppuyopo/220812390807