[codility] PassingCars

(문제) 주어진 배열 A에서 서로 만나는 차 쌍의 개수를 세는 함수

 

(my solution)

- 문제를 이해하는데 오랜 시간이 걸렸다.. (west, east도 헷갈리고 난리)

- 배열 역순으로 순회하면서 east(0) 값을 찾고 west(1)를 잘 count만 하면 된다. (굳이 역순으로 할 필욘 없었구나;;)

- 가장 간단한 케이스부터 꼼꼼하게 테스트를 하니 버그를 줄이는 데 도움이 많이 된다.

- for문이 헷갈리면 표를 그려놓고 i 값이 변할 때마다 다른 변수의 값이 변하는 걸 따라하다 보면 실수를 줄일 수 있다.

- 시간복잡도는 O(N)

package codility.tasks;

public class PassingCars {
    public static int solution(int[] A) {
        int pairCount = 0;
        int foundedEastCar = 0;
        int lastIndex = A.length - 1;

        for (int i = lastIndex; i >= 0; --i) {
            if (pairCount > 1000000000) {
                return -1;
            }

            if (A[i] == 0) {
                // East
                pairCount += (lastIndex - i - foundedEastCar);
                foundedEastCar++;
            }
        }

        return pairCount;
    }
}

 

(chatGPT)

- 나는 West 값을 Count해서 pairCount 계산식이 조금 복잡했는데 East 값을 Count하는 게 훨씬 심플하군! 아쉽다.

class Solution {
    public int solution(int[] A) {
        int totalEastCars = 0;
        int passingPairs = 0;

        for (int car : A) {
            if (car == 0) {
                totalEastCars++;
            } else {
                passingPairs += totalEastCars;
                if (passingPairs > 1000000000) {
                    return -1;
                }
            }
        }

        return passingPairs;
    }
}