[Codility] Lesson 5 : PassingCars (Java)

문제요약

만들 수 있는 (0, 1) 쌍의 개수를 구하시오.

 

풀이

배열을 순회하면서 0의 개수를 누적해서 더하고, 1을 만나면 누적된 0의 개수를 더한다.

 

코드

시간복잡도 O(N)

public static int solution(int[] A) {
    int pairs = 0;
    int count_zero = 0;

    for (int n : A) {
        if (n == 0) {
            count_zero++;
        } else if (n == 1) {
            pairs += count_zero;
        }

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

    return pairs;
}

 

출처 : https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/