PassingCars (누적합)

비어 있지 않은 정수 배열 A가 주어집니다. 
배열 A의 연속된 원소들은 도로 위를 달리는 연속된 자동차를 나타냅니다.

배열 A는 0과 1로만 이루어져 있습니다:

- 0은 동쪽으로 가는 자동차를 의미합니다.
- 1은 서쪽으로 가는 자동차를 의미합니다.

목표는 지나치는 자동차 쌍을 세는 것입니다.
우리는 (P, Q)라는 자동차 쌍이 다음 조건을 만족할 때 "지나친다(passing)"라고 정의합니다:

0 ≤ P < Q < N,  
그리고 P는 동쪽으로 가고 (A[P] = 0),  
Q는 서쪽으로 가는 경우 (A[Q] = 1).

예시:
배열 A가 다음과 같을 때:

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

이 경우 지나치는 자동차 쌍은 다음과 같습니다:
(0,1), (0,3), (0,4), (2,3), (2,4)

총 5쌍이므로 결과는 5입니다.

---

구현 조건:

다음 함수를 작성하세요:

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

이 함수는 배열 A가 주어졌을 때, 지나치는 자동차 쌍의 개수를 반환합니다.  
만약 쌍의 개수가 1,000,000,000을 초과하면 -1을 반환해야 합니다.

---

추가 조건:

- N의 범위: [1..100,000]
- 배열 A의 각 원소는 0 또는 1만 가질 수 있습니다.

public class PassingCars
{
    // O(n^2) 버전
    public int solution(int[] A)
    {
        // 결국, 동쪽으로 가는차의 인덱스를 찾고,
        // 그 인덱스 뒤에 서쪽으로 가는 차의 개수를 세면 된다.
 
        int passingCount = 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)
                    {
                        passingCount++;
 
                        if (passingCount > 1000000000)
                            return -1;
                    }
                }
            }
        }
 
        return passingCount;
    }
 
    // O(n) 버전
    public int solution2(int[] A)
    {
        int passingCount = 0;
        int eastCarCount = 0;
 
        for (int i = 0; i < A.Length; i++)
        {
            if (A[i] == 0)
            {
                // 동쪽으로 가는 차의 개수를 세고,
                eastCarCount++;
            }
            else
            {
                // 서쪽으로 가는 차를 만날 때마다 동쪽으로 가는 차의 개수를 더해줌
                passingCount += eastCarCount;
 
                if (passingCount > 1000000000)
                    return -1;
            }
        }
 
        return passingCount;
    }
}