[JavaScript/알고리즘] PassingCars (누적값 문제)

Lesson 5 (Prefix Sums) - PassingCars(Easy)

Test results - Codility

점수: 40/100

 

도로와 차들이 있다. 차는 값이 0일때 동쪽, 1일때 서쪽으로 움직인다.

위의 그림처럼 A[0] = 0 A[1] = 1 A[2] = 0 A[3] = 1 A[4] = 1일때, 차가 만나는 경우(쌍)은 각각

(0, 1), (0, 3), (0, 4), (2, 3), (2, 4) 이다.

이와 같은 쌍이 총 몇 가지가 나오는지 구한다.

 

시도(실패)

function solution(A) {
    let count = 0;
    const basicDirectionCarNums = [];

    A.forEach((direction, index) => {
        if (direction === A[0]) {
            basicDirectionCarNums.push(index);
        }
    });

    for (carNum of basicDirectionCarNums) {
        for (let i = Number.parseInt(carNum) + 1; i < A.length; i++) {
            if (A[carNum] !== A[i]) {
                count++;
            }
        }
    }

    return count;
}

첫번째 차의 방향을 구해서 그 차와 같은 방향으로 가는 차들을 구하고, 그 이후에 오는 다른 방향의 차가 몇 대인지 세는 방법을 써보았다. 결과는 오류+시간복잡도 문제로 실패...

 

 

모범답안

function solution(A) {
    let count = 0;
    let eastCars = 0;
    
    for (carNum of A) {
        if (carNum === 0) {
            eastCars++;
        } else {
            count += eastCars;
        }
        
        if (count > 1000000) {
            return -1;
        }
    }
    
    return count;
}

 

쌍을 이루려면 무조건 동쪽으로 가는 차와 서쪽으로 가는 차가 만나야 한다.

그래서 반복문을 돌면서 동쪽으로 가는 차를 센다음, 서쪽으로 가는 차를 만나면 result에 동쪽으로 가는 차들의 누적값을 더하는 식으로 해결한다.

예를 들어, 위의 그림에서 A[1] 시점에선 동쪽으로 가는 차가 1대였고, A[3] 시점에선 2대이므로 1+2+2 = 5 라는 식이다.

알고리즘을 짜기 쉬운 간단한 규칙을 찾으면 되는 문제였다.

 

그리고 동쪽을 기준으로 한 이유는, 인덱스를 증가시키며 배열을 순회하기 때문이다.

 

문제 의미가 알기 어려워서 많이 헤맸음...