[Codility] PassingCars

문제

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

N개의 정수로 구성된 비어 있지 않은 배열 A가 있다. 배열 A의 연속된 요소는 도로 위의 연속된 자동차를 나타내며, 배열 A에는 0 또는 1로만 구성되어 있다. 이때, 0은 동쪽으로 이동하는 차량을 나타내고 1은 서쪽으로 이동하는 차량을 나타낸다.

목표는 지나가는 차를 세는 것으로, P가 동쪽으로 이동하고 Q가 서쪽으로 이동할 때 0 ≤ P < Q < N인 한 쌍의 차 (P, Q)가 지나간다고 한다.

예로 들어 아래와 같은 배열 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)이다. 즉, 차의 쌍 (P, Q)에 대한 배열 값이 0, 1인 것을 찾으면 된다.

참고로 지나가는 차량 쌍 수가 1,000,000,000을 초과하면 -1을 반환한다.

 

 

풀이

단순하게 배열을 순회하며 동쪽으로 가는 차량, 즉 값이 0인 개수를 세다가, 서쪽으로 가는 차량인 1을 만나면 0의 수를 결과값에 더하는 방식으로 풀어낼 수 있다.

def solution(A):
    # 반환값
    result = 0
    # 동쪽으로 가는 차의 수
    east = 0
    
    # 배열 순회
    for a in A:
        # 동쪽으로 가는 경우
        if a == 0:
            east += 1
        # 서쪽으로 가는 경우
        elif a == 1:
            # 결과값 갱신
            result += east
        
        # 제한 수 초과 시
        if result > 1000000000:
            return -1
    return result

 

 

참고 문서

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