Table of contents

코딜리티 PassingCars

배열에서 (0, 1)의 값을 이룰 수 있는 요소들의 개수를 구하는 문제이다.

첫번째 풀이

O(N^2)

private int passingCars(int[] A) {
    int count = 0;
    Set<int[]> ints = makePairs(A);
    int size = ints.size();
    return size > 1000000000 ? -1 : size;
}

private Set<int[]> makePairs(int[] A) {
    Set<int[]> pairs = new HashSet<>();
    for (int i = 0; i < A.length; i++) {
        for (int k = i + 1; k < A.length; k++) {
            if (A[i] == 0 && A[k] == 1) {
                int[] pair = new int[2];
                pair[0] = i;
                pair[1] = k;
                pairs.add(pair);
            }
        }
    }

    return pairs;
}

(0, 1) 쌍을 Set에 넣고 사이즈를 반환한다. 역시나 복잡도 개선이 필요하다.

두번째 풀이

O(N^2)

private int passingCars2(int[] A) {
    int count = 0;
    for (int i = 0; i < A.length; i++) {
        if (A[i] == 0) {
            for (int j = i + 1; j < A.length; j++) {
                if (A[j] == 1) {
                    count++;
                }
            }
        }
    }

    return count > 1000000000 ? -1 : count;
}

0 뒤에 나타나는 1을 세는 방식으로 했으나, 공간복잡도만 줄어들었을 뿐 시간복잡도는 마찬가지로 O(n^2) 이며, time out에 걸리기 때문에 O(n) 이 필요하다.

세번째 풀이

O(n)

처음에는 0을 기준으로 다음 0을 만났을 때 count 값을 조정하면 될 것 같았다. 하지만, 코드 복잡도가 너무 증가해 포기했다.

다음으로 1을 기준으로 생각해봤다. 1을 기준으로 생각한다면 자신의 앞에 존재하는 0의 개수 자체가 (0, 1) 쌍을 이룰 수 있는 개수가 된다. 먼저 코드를 살펴보자.

private int passingCars3(int[] A) {
    int zeroCount = 0;
    long count = 0;

    for (int i = 0; i < A.length; i++) {
        if (A[i] == 0) zeroCount++;
        else {
            count += zeroCount;
        }
    }

    return count > 1000000000 ? -1 : (long) count;
}

0을 누적하면서 1을 만나면 count에 누적된 0의 개수를 누적한다. 예를 살펴보자.

A[0] = 0 A[1] = 1 A[2] = 0 A[3] = 1 A[4] = 1

  • 0: zeroCount++
    • zeroCount = 1, count = 0
  • 1: count += zeroCount
    • zeroCount = 1, count = 1
  • 0: zeroCount++
    • zeroCount = 2, count = 1
  • 1: count += zeroCount
    • zeroCount = 2, count = 3
  • 1: count += zeroCount
    • zeroCount = 2, count = 5

정리

이번 문제에서는 주의해야할 부분이 있었다.

The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.

카운트 값이 10억을 넘어가면 -1을 반환하라고 한다. 일종의 힌트인 셈이다. 이 부분을 놓치고 count 변수를 int로 선언한다면 90 점이 나온다. Integer.MAX_VALUE가 대략 20억 정도인데, count를 int로 선언한 경우 하나의 테스트 케이스에서 overflow가 발생한다.