[Codility] Lesson5. PassingCars - 문제풀이

Description

N개의 정수로 구성된 비어 있지 않은 배열 A가 주어집니다. 배열 A의 연속 요소는 도로에서 연속된 자동차를 나타냅니다. N개의 정수가 주어지면 통과 자동차 쌍의 수를 반환합니다.

A non-empty array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.

Array A contains only 0s and/or 1s:

0 represents a car traveling east,1 represents a car traveling west.

The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.

For example, consider array A such that:

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

We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A of N integers, returns the number of pairs of passing cars.

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

For example, given:

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

the function should return 5, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];each element of array A is an integer that can have one of the following values: 0, 1.

Solution 1. prefix Sum

public int solution(int[] A) {
    int len = A.length;
    int cnt = 0;

    int[] dp = new int[len];
    dp[0] = A[0];
    for(int i = 1; i < len; i++){
        dp[i] = dp[i-1] + A[i];
    }

    for(int i = 0 ; i<len; i++){
        if(A[i] == 0){
            cnt += dp[len-1] - dp[i];
            if(cnt > 1000000000)return -1;
        }
    }
    return cnt;
}

prefix sum을 계산하여 각 요소까지의 누적 합을 기억해 놓고0일경우 끝에서부터 해당위치까지의 1의 누적합을 더해 나갑니다.

• 시간복잡도 : O(n)

Reference

PassingCars coding task - Learn to Code - Codility