Codility Lesson 05 - CountDiv( JAVA )

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

CountDiv coding task - Learn to Code - Codility

 

문제

- A와 B사이의 정수 중( A, B 포함 ) K로 나누어 떨어지는 정수들의 개수를 구하라.

 

제한조건

• 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는 0 ~ 2,000,000,000 사이의 정수이다.

K는 1 ~2,000,000,000 사이의 정수이다.

A <= B

 

풀이

- for문으로 순회 시 timeout 발생 예상 예시 : [0, 2,000,000,000, 1]

- A와 B를 K로 나누었을 때 몫을 활용

- A == B일 경우를 맨처음 예외 케이스로 빼준다.

- 예시에서 A=6, B=11, K=2

- mok1 = A / K, mok2 = B / K라 했을 때 아래와 같은 특징이 발견된다.

[7, 11, 2] - 3 5 - 2 둘다 나누어 떨어지지 않는 경우에는 그대로
[6, 10, 2] - 3 5 - 3 둘다 나누어 떨어지는 경우에는 +1
[6, 11, 2] - 3 5 - 3 B만 나누어 떨어지지 않는 경우에는 +1

[7, 15, 3] - 2 5 - 3 A만 나누어 떨어지지 않는 경우에는 그대로

그대로는 answer = mok2 - mok1 / +1은 answer = mok2 - mok1 + 1을 의미한다.

 

예상 시간복잡도 : O(1) - 계산식만으로 풀이했기에...

 

소스코드

// 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 A, int B, int K) {
        // write your code in Java SE 8
        if( A == B ){
            if( A % K == 0) return 1;
            else return 0;
        }

        int answer = 0;
        int mok1 = A / K;
        int mok2 = B / K;

        boolean mok1Check = A % K == 0?true:false;
        boolean mok2Check = B % K == 0?true:false;

        if( (mok1Check && mok2Check) || (mok1Check && !mok2Check) ){
            answer = mok2 - mok1 + 1;
        }else{
            answer = mok2 - mok1;
        }

        return answer;
    }
}

풀긴했는데.. 전에는 더 쉽게 풀었던 것으로 기억했는데 1시간이 넘게 걸렸다.. 흠...

 

간결하게 설명된 블로그를 참고하시길

https://dirmathfl.tistory.com/21

Lesson 5: Prefix Sums → Count Div