[Codility] CountDiv

문제

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

CountDiv coding task - Learn to Code - Codility

 

---

수학 문제에 가까웠던 문제 같다.

 

try #1 (62/100)

class Solution {
    public int solution(int A, int B, int K) {
        int cnt=0;
        int index = K*(A/K)+K;
        if(A%K==0) index = A;
        
        for(int i=index;i<=B;i+=K) {
            cnt++;
        }
        return cnt;
    }
}

처음은 역시 반복문을 썼다..

A to B까지 다 돌면 timeout 날까봐 i++가 아닌 K씩 더하는걸로 했다.

A와 B 사이면서 i mod K = 0 을 충족시키는 값을 index에 저장하고,

index to B까지 K를 더해서 cnt를 구했다.

 

결과는 정확도는 100프로지만 일부 timeout error ㅠㅠ

다른 풀이 방식을 생각해보았다.

 

try #2 (87/100)

class Solution {
    public int solution(int A, int B, int K) {
        int answer = B/K-(A-1)/K;
        if(A==0) answer++;
        return answer;
    }
}

훨씬 간단해졌다.

• B 이하에서 i mod K = 0을 충족하는 숫자는 B/K개
• A 미만에서 i mod K = 0을 충족하는 숫자는 (A-1)/K개

위 두 가지를 구하고, A가 0인 경우에는 0 mod K의 결과가 무조건 0인 것을 감안해 +1을 해줬다.

하지만 A=0, K=2000000000, K=1인 경우에서 답이 틀렸다.

 

코드를 차근차근 되짚어보니 A가 1보다 작은 경우 즉, A=0인 경우에 오류가 났다.

B/K-(A-1)/K 식에서 A가 0이면 양수-음수 형태가 되어 결국 양수+양수로 계산되는 것이다.

 

try #3 (100/100)

class Solution {
    public int solution(int A, int B, int K) {
        int answer ;
        if(A<1) {
            answer = B/K+1;
        } else {
            answer = B/K-(A-1)/K;
        }
        return answer;
    }
}

answer에 들어가는 값을 바꿔주었다.

풀이 완료! 시간복잡도는 깔끔한 O(1)