[Codility] Lesson 5: Prefix Sums - PassingCars (javascript) 문제 풀이

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

Task description

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

PassingCars coding task - Learn to Code - Codility

 

- N 개의 비어있지 않은 배열 A 제공
- 배열 A의 연속적인 요소는 도로의 연속된 자동차를 나타냄
- 배열 A에는 0 또는 1만 포함됨
0은 동쪽으로 여행하는 자동차
1은 서쪽으로 여행하는 자동차
- 목표는 지나가는 자동차를 세는 것
- P가 동쪽으로 여행하고 Q가 서쪽으로 여행할 때, 0 ≤ P < Q < N인 한 쌍의 자동차 (P, Q)가 지나가고 있다고 함
- 통과하는 자동차 쌍의 수를 return
- 통과하는 자동차 쌍의 수가 1,000,000,000을 초과하면 함수는 -1을 return
- 가장 효율적인 알고리즘 작성

 

Solution

CASE 1: 배열 A의 끝에서부터 개수 체크 - 70%

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let west_cars = 0;
    let passing_cars = 0;
    
    for(let i=A.length-1; i>=0; i--){
        switch(A[i]){
            case 0:
                passing_cars += west_cars;
                break;
            case 1:
                west_cars++;
                break;
        }
    }
    
    return passing_cars;
}

- west_cars : 서쪽으로 가는 차의 개수(A[i]의 값이 1인 개수)
- passing_cars : 전체 통과하는 자동차 쌍의 개수

- 배열 A의 끝에서부터 1의 개수를 카운트
- 0이 나올 때마다 해당 시점의 카운트 값을 더해줌

 

CASE 1: Result

 

CASE 1: Analysis

The following issues have been detected: wrong answers.
다음과 같은 문제가 감지되었습니다. 오답.

=> 정확성은 일치하지만 효율성 측면에서 오류 발생
=> 통과하는 자동차 쌍의 수가 1,000,000,000을 초과하면 함수는 -1을 return 필요

 

CASE 2: 배열 A의 끝에서부터 개수 체크 (예외 처리) - 100%

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let west_cars = 0;
    let passing_cars = 0;
    
    for(let i=A.length-1; i>=0; i--){
        switch(A[i]){
            case 0:
                passing_cars += west_cars;
                break;
            case 1:
                west_cars++;
                break;
        }
        if(passing_cars > 1000000000){
            return -1;
        }
    }
    
    return passing_cars;
}

- west_cars : 서쪽으로 가는 차의 개수(A[i]의 값이 1인 개수)
- passing_cars : 전체 통과하는 자동차 쌍의 개수
- 배열 A의 끝에서부터 1의 개수를 카운트
- 0이 나올 때마다 해당 시점의 카운트 값을 더해줌
- CASE 1에서 passing_cars가 1,000,000,000을 초과하는 경우 -1을 return하도록 추가

 

CASE 2: Result

 

CASE 2: Analysis

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

 

결론

이 문제는 생각보다 단순하다.

0을 기준으로 두고 1의 개수를 더해가며 계산하기 위해 배열의 끝에서부터 시작했지만, 1을 기준으로 두고 0의 개수를 더해가며 계산하면 배열의 앞에서부터 시작하면 된다.

그리고 for문을 돌며 passing_cars를 계산하다가 passing_cars의 값이 1,000,000,000을 초과하는 경우 -1을 return하도록 해주면 된다.


for문을 한 번 돌리는 것은 O(N)이므로 성능에 크게 문제가 없는 것으로 확인됐다.