Lesson 5: Prefix Sums → Passing Cars

문제

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

PassingCars coding task - Learn to Code - Codility

리스트 내의 자동차 방향(east: 0 , west :1)이 주어질 때, 각 방향이 쌍을 이루는 횟수를 찾는 문제이다. 만약 인덱스 3에서 east로 가는 자동차가 있다면, 인덱스 3 이후로의 자동차들만 쌍을 이루는지 확인하고, 앞 부분은 확인하지 않아도 된다.

---

문제 풀이

Figure 1: 문제의 기본 예제

그림 1은 문제의 기본 예제에서 값을 도출하는 과정이다.

0 (east)로 가는 자동차와 1 (west)로 가는 자동차는 짝을 이룰 수 있다. 따라서 리스트의 각 방향에 따라 짝을 이루는지 확인하는 과정은 0의 횟수에 따라 달라진다.

 

그림과 같이 인덱스 2에서 0이 다시 등장하므로, 이전의 값과는 쌍을 이루지 않고 0이 발생한 이후의 값과 쌍을 이루는지 확인하는 과정이 필요하다. 처음에 생각했을 때는 0의 위치를 찾고 0의 위치 이후의 값들을 순차적으로 탐색하면 되지 않을까 생각하였다. 하지만 0이 등장하면 그림 1과 같이 카운트가 중복되므로 0의 횟수에 따라 카운트 수를 증가시켜주면 한번의 탐색으로 모든 쌍을 찾을 수 있다.

 

---

코드

EAST = 0
WEST = 1


def solution(A):
    answer = 0
    cnt = 0

    for dir in A:
        if dir == EAST:
            cnt += 1
        else:
            answer += cnt
            
    if answer > 1000000000:
        return -1
        
    return answer