[Codility] Lesson 5: Prefix Sums - CountDiv (javascript)

깃허브 : https://github.com/miiingo/codility

Task description

원본 사이트 : https://app.codility.com/programmers/lessons/5-prefix_sums/count_div/

CountDiv coding task - Learn to Code - Codility

- 세 개의 정수 A, B, K가 주어지면 [A..B] 범위 내에서 K로 나눌 수 있는 정수의 수를 return
- { i : A ≤ i ≤ B, i mod K = 0 }
- 가장 효율적인 알고리즘 작성
- A, B : [0..2,000,000,000] 범위의 정수
- K : [1..2,000,000,000] 범위의 정수

 

Solution

CASE 1: for문을 돌려 count 체크 - 50%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A, B, K) {
    // write your code in JavaScript (Node.js 8.9.4)
    let count = 0;
    
    for(let i=A; i<=B; i++){
        if(i%K == 0){
            count++;
        }
    }
    
    return count;
}

- A~B까지 for문을 돌며 mod 값이 0이면 count 값 증가
- count 값 return

 

CASE 1: Result

 

CASE 1: Analysis

The following issues have been detected: timeout errors.
For example, for the input [0, 2000000000, 1] the solution exceeded the time limit.
다음과 같은 문제가 감지되었습니다. 시간 초과 오류.
예를 들어, 입력 [0, 2000000000, 1]의 경우 솔루션이 시간 제한을 초과했습니다.

 

CASE 2: 나눗셈 몫 이용 (예외 처리 X) - 12%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A, B, K) {
    // write your code in JavaScript (Node.js 8.9.4)
    const resultA = Math.floor(A / K);
    const resultB = Math.ceil(B / K);
    const result = resultB - resultA;
    
    return result;
}

- resultA : A / K의 몫을 올림한 정수
- resultB : B / K의 몫을 올림한 정수

 

CASE 2: Result

 

CASE 2: Analysis

The following issues have been detected: wrong answers.
For example, for the input [0, 0, 11] the solution returned a wrong answer (got 0 expected 1).
다음과 같은 문제가 감지되었습니다. 오답.
예를 들어, 입력 [0, 0, 11]의 경우 솔루션에서 잘못된 답변을 반환했습니다 (예상 0이 예상 됨 1).

 

CASE 3: 나눗셈 몫 이용(예외 처리 추가) - 50%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A, B, K) {
    // write your code in JavaScript (Node.js 8.9.4)
    const resultA = Math.ceil(A / K);
    const resultB = Math.ceil(B / K);
    let result;
    
    if(A < B){
        result = resultB - resultA;
    }
    if(A == B){
        if(A == 0){
            result = 1;
        }
        else if(A < K){
            result = 0
        }
        else{
            result = 1;
        }
    }
    
    return result;
}

- resultA : A / K의 몫을 올림한 정수
- resultB : B / K의 몫을 올림한 정수
- 예외처리 추가
    A==B==0이면 result는 1
    A==B<K이면 result는 0
    A==B>=K이면 result는 1

 

CASE 3: Result

 

CASE 3: Analysis

The following issues have been detected: wrong answers.
For example, for the input [0, 14, 2] the solution returned a wrong answer (got 7 expected 8).
다음과 같은 문제가 감지되었습니다. 오답.
예를 들어, 입력 [0, 14, 2]에 대해 해답이 틀린 답을 반환했습니다 (결과: 7, 정답: 8).

=> 예외 처리 부족

 

CASE 4: 나눗셈 몫 이용 - 100%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A, B, K) {
    // write your code in JavaScript (Node.js 8.9.4)
    const resultA = Math.ceil(A / K);
    const resultB = Math.ceil((B+1) / K);
    const result = resultB - resultA;
    
    return result;
}

- resultA : A / K의 몫을 올림한 정수
- resultB : (B+1) / K의 몫을 올림한 정수
- 올림(Math.ceil) 이용
- B의 나눗셈 결과도 count에 포함되도록 하기 위해 (B+1)을 K로 나눔

 

※ 내림(Math.floor)을 이용할 경우 (A-1)/K가 필요 (결과는 동일!)

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A, B, K) {
    // write your code in JavaScript (Node.js 8.9.4)
    const resultA = Math.floor((A-1) / K);
    const resultB = Math.floor(B / K);
    const result = resultB - resultA;
    
    return result;
}

 

CASE 4: Result

 

CASE 4: Analysis

The solution obtained perfect score.
이 솔루션은 완벽한 점수를 얻었습니다.