[Codility] Prefix Sums - PassingCars 풀이

예문


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

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.

해석

  • 배열 A : N개의 정수로 이루어짐
  • A의 요소들은 도로상의 차들을 의미함.
    • 0 : 동쪽으로 여행하는 차
    • 1 : 서쪽으로 여행하는 차
  • (P, Q) : P는 동쪽으로 여행하는 차, Q는 서쪽으로 여행하는 차
  • 0 ≤ P < Q < N
  • 지나가는 차의 짝의 수를 리턴하라!

풀이

  • P보다 작은 값은 제외
  • (동쪽으로 이동하는 차) * (그 이후에 서쪽으로 이동하는 차)
  • ex) A[0] = 0, A[1] = 1, A[2] = 0, A[3] = 1, A[4] = 1
  • A[0] 동쪽으로 이동 차량 + 1
  • A[1] 동쪽으로 이동 차량 * 서쪽으로 이동하는 차 = 1 * 1 => 1
  • A[2] 동쪽으로 이동 차량 + 1
  • A[3] 동쪽으로 이동 차량 * 서쪽으로 이동하는 차 = 2 * 1 => 2
  • A[4] 동쪽으로 이동 차량 * 서쪽으로 이동하는 차 = 2 * 1 => 2
  • 총합 5

제약사항

  • N의 범위는 정수 [1..100,000]
  • A의 각 요소의 값은 0, 1 중의 하나를 가진다.

코드

public int solution(int[] A) {
  int pCount = 0;
  int sum = 0;
  for (int i = 0; i < A.length; i++) {
    if (0 == A[i]) pCount++;
    else {
      sum += pCount * A[i];
      if (sum > 1000000000) return -1;
    }
  }
  return sum;
}

결과