Codility Lesson 05 - PassingCars( JAVA )

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

PassingCars coding task - Learn to Code - Codility

 

문제

- 비어있지 않은 A배열은 N개의 정수들로 이루어져 있다.

- 연속적인 A배열의 원소들은 길 위의 연속적인 차들을 나타낸다.

- A는 0과 1로만 이루어져 있고, 0은 동쪽( east )로 여행하는 차를 나타내며, 1은 서쪽( west )로 여행하는 차를 나타낸다.

- 차들의 짝을 ( P, Q ), 조건 : 0 <= P < Q < N일 때, P는 동쪽( east )으로 갈 때, 마주치는 Q의 인덱스를 쌍으로 나타낸다.

- 예시, A = [0, 1, 0, 1, 1]

east로 향하는 차는 index 기준으로 0, 2이다.

0 : index기준으로 1, 3, 4 -> (0, 1), (0, 3), (0, 4)

2 : index기준으로 3, 4 -> (2, 3), (2, 4)

- the number of pairs of passing cars exceeds 1,000,000,000. -> 1,000,000,000이 넘어가면 return -1을 한다.

 

제한조건

• 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.

N은 1 ~ 100,000사이의 정수이다.

A의 각 원소는 0 or 1만 가질 수 있다.

 

풀이

- east로 가는 차가 마주치는 west로 가는 차량의 쌍의 수만이 중요하다는 점에서 착안( P < Q )일 때

- 예시 기준으로 설명

east로 향하는 차는 0, 2( index 기준으로 )

for문으로 순회 할 때, 

index 0 : 동쪽으로 가는 차량 1대 -> eastCar = 1

index 0 ~ 1 : 서쪽으로 가는 차량 수 * eastCar = 1

index 2 : 동쪽으로 가는 차량이 2대가 됨 -> eastCar = 2

index 2 이후 : 서쪽으로 가는 차량 수 * eastCar = 4

따라서 return 5( 1 + 4 )

 

예상 시간복잡도 : O(N) - for문 순회를 한번만 한다