Codility Lesson5 - PassingCars

🔍 문제

---

 

PassingCars coding task - Learn to Code - Codility

 

✏️ 풀이 - JS

---

function solution(A) {
    const pArr = []; //0인 A의 idx배열
    const qArr = []; //1인 A의 idx배열

    let carCnt = 0;

    for(let i in A) {
        if(A[i] === 1) {
            qArr.push(i);
        } else {
            pArr.push(i);
        }
    }

    //짝이 없는경우
    if(pArr.length === 0 || qArr.length === 0) {
        return carCnt;
    }


    for(let i in pArr) {
        for(let j in qArr) {
            if(pArr[i] < qArr[j]) {
                carCnt += qArr.length-j;
                break;
            } else {
                continue;
            }
        }
    }

    return carCnt;
}

기본 로직은 0과 1의 idx를 따로 배열로 빼놓은 다음에 Q idx가 P idx보다 클 경우 차의 개수를 늘리는 방식으로 접근하였다. 이중 for문을 쓰면 시간 초과될 걸 알고 있었지만 정확도라도 맞춰보려고 생각나는대로 써보았다. 결과는 정확도 60% 효율성은 0% 나올줄 알았는데 20%나와서 총 40%가 나왔다....

 

 

다른 사람들의 해답을 찾아보니 훨씬 더 쉽고 간단한 로직으로 푼 것을 알 수 있었다.

배열 A에 0, 1 값이 연속으로 랜덤하게 배치 됐을 때, 1의 입장에서는 내 인덱스 앞에 0이 몇개 있느냐에 따라 가능한 pair의 수가 정해진다. 따라서 배열 값을 한개씩 순회하며, 0일때는 zeroCnt의 갯수를 하나씩 늘려주고, 1인 경우에는 zeroCnt를 기준으로 carCnt(=pair)에 합해준다.

 

이를 기반으로 코드는 아래와 같이 짰다. 시간복잡도는 당연히 O(N)이 나왔고 정확도, 효율성 모두 100%가 나왔다.

function solution(A) {
    let zeroCnt = 0;
    let carCnt = 0;

    for(let i in A) {
        if(A[i] === 0) {
            zeroCnt += 1;
        } else {
            carCnt += zeroCnt;
        }

        if(carCnt > 1000000000) {
            return -1;
        }
    }

    return carCnt;
}

알고리즘도 풀다보면 정말 느는걸까? 이렇게 쉽고 심플한 로직이 있었는데 나는 왜 생각하지 못했나...흑 부끄럽다.