코딜리티 | lesson5 - Prefix Sums : PassingCars(python)

💻lesson5 - PassingCars

1. 문제

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:

def solution(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:

2. 문제 접근

지나친 차의 수를 구하는 문제이다.

EX)

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

A[0] = 동쪽으로 간 차
: 동쪽으로 가고 있는 차 = 1, passing = 0
A[1] = 서쪽으로 간 차
: 동쪽으로 가고 있는 차 = 1, 동쪽 차는 1대이기 때문에 passing은 1
A[2] = 동쪽으로 간 차
: 동쪽으로 가고 있는 차 = 2, 지나칠 차 없기 때문에 passing 0
A[3] = 서쪽으로 간 차
: 동쪽으로 가고 있는 차 = 2, 따라서 동쪽 차가 2대이기 때문에 2번 지나칠 것임. passing = 2
A[4] = 서쪽으로 간 차
: 동쪽으로 가고 있는 차 = 2, 따라서 동쪽 차가 2대이기 때문에 2번 지나칠 것임. passing = 2

총 passing 의 합이 정답이다.
passing이 1000000000일 경우 -1을 출력하는 조건도 추가한다.

3. 첫번째 시도 - python

def solution(A):
    passing = 0
    east = 0

    for car in A:
        if(car==0):
            east+=1
        elif(car==1):
            passing += east
        
    if(passing > 1000000000): return -1
    return passing

4. 첫번째 결과

5. 마무리

솔직히 처음 문제 봤을 때 문제 이해가 안되서 도저히 문제를 풀 수 없어 다른 사람의 문제 해설을 보고나서야 문제 풀이를 시작할 수 있었다.
문제 이해 마저 코테에 중요한 역량일텐데 아직 난 미숙한 모양이다.
조금 더 문제에 집중해서 이해해보려는 태도를 가지도록 하자