Codility - CountDiv

https://app.codility.com/c/run/trainingCH5S84-MK4/

Codility

 

이번 문제는 직관적으로 이해는 쉬웠으나 시간 복잡도가 중요한 문제였고 역시나 coner case를 조심해야하는 문제다. 

 

prefix Sum(부분합) 문제

• 이중 for문 절대로 안됨
• 단건의 for문도 전체 index를 돌면 시간 복잡도 실패
• corner case 확인 잘할 것

public int solution(int A, int B, int K) {

    int startIdx = 0;
    int result = 0;

    for (int i = A; i <= B; i++) {
        if (i % K == 0) {
            startIdx = i;
            result++;
            break;
        }
    }

    result += (B - startIdx) / K;

    if(B == A && B % K != 0) {
        return 0;
    }

    return result;
}

이번 문제의 코너 케이스는 A<=B일 때 A, B가 0일 때 였다.