Codility - PassingCars [Python]

 문제

 

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

PassingCars coding task - Learn to Code - Codility

 

 

 

 

 

 문제 상황

 

- 배열 A는 i번째에서 출발하는 차들의 이동 방향을 알려주는 배열이다. 즉, A[2] = 0 이면 2에서 출발하여 동쪽으로 이동하는 차라는 의미가 된다. 문제의 조건에 없지만 출발 시간은 동시라고 설정하고, 추월은 없다고 가정해야 문제가 성립한다. 

 

 

 

 

 

 해결 전략

1

- 결과적으로 1의 개수를 구하는 문제인데 구분점은 0이 된다. 즉, 어떤 서쪽으로 가는 차가 나왔을 때, 이 차가 만날 수 있는 차들은 출발위치 이전에서부터 동쪽으로 진행하는 차들의 수이다. 

 

 

 

 

 

 코드

 

def solution(A):
    cars_to_east = 0 # 동쪽으로 가는 차의 수
    num_cross = 0 # 마주치는 횟수
    max_cross = 1000000000
    for i in range(len(A)):
        if A[i] == 0 : cars_to_east += 1
        else: num_cross += cars_to_east
    return num_cross if num_cross <= max_cross else -1

 

 

 

 

 

 해설

 

- 배열을 순회하며 0의 개수를 세고, 1을 만났을 경우 그 이전에 출발한 차 중 동쪽으로 진행하는 차의 개수, 즉 0의 개수를 더해준다. O(N)의 속도로 해결 가능하다.

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 알고리즘 자체는 매우 쉬운 문제였지만 문제 이해가 너무 어려웠다. 고등학교 물리 문제에 대한 기억 때문에 더 이해하기 어려웠던 부분이, i에서 출발한다는 정보나 속도에 대한 정보가 전무해서 다른 사람들의 문제 해설을 보고 이해하였다. 하지만 알고리즘 자체는 해결 방법을 찾는데 어렵지 않았다.