Codility Lesson5 - CountDiv

🔍 문제

---

 

CountDiv coding task - Learn to Code - Codility

 

✏️ 풀이 - JS

---

일단 문제 자체는 쉽다. 주어진 범위내에서 어떤 정수 값으로 나누어 떨어지는 수의 개수를 구하면 되는 문제다.
단순하게 생각하면 아래와 같이 풀면되지만, 문제에서 가장 중요한건 효율적으로 풀어야 하기 때문에 performance면에서 0%이다.

function solution(A, B, K) {
    let cnt = 0;

    for(let i = A; i <= B; i++) {
        if( i % K === 0 ) cnt++; 
    }

    return cnt;

}

범위가 0부터 B 까지라면, 단순하게 K로 나눈 몫을 return 하면된다. 그렇다면 A에서 B까지 범위는?! 0에서 B까지의 범위에서 K로 나눈 몫 - 0에서 A까지 나눈 몫을 계산하면 되지 않을까?

function solution(A, B, K) {
    let cnt = parseInt(B / K) - parseInt(A / K);
    if(A % K === 0) cnt += 1;
    return cnt;
}

중간의 if문은 만약 A도 K의 배수일 경우 let cnt = parseInt(B / K) - parseInt(A / K)식에서 같이 빼기가 되기 때문에 다시 1개를 더해준다. 시간 복잡도는 O(1), 정확도, 효율성 모두 100%가 나왔다.