합을 이용한 알고리즘

아래 문제는 코딜리티에서 제공하는 Passing Cars의 문제입니다🧑🏻‍💻

 

문제 제시

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:
    public func solution(_ A : inout [Int]) -> Int
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:
    - 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.

문제 해결

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var sumOfGivenData = A.reduce(0, +)
    var resultSum = 0
    
    for index in A {
        if index == 0 {
            resultSum += sumOfGivenData
        }
        else {
            sumOfGivenData -= 1
        }
    }
    
    return resultSum > 1000000000 ? -1 : resultSum
}

 

사용된 개념

 - reduce (Array Sum)

 - 반복/조건문

 - 삼항연산자

 

문제 뒷담화

해당 문제는 되게 쉬웠는데 사실 코딜리티의 여러 문제들이 그러하지만 원어를 가지고 이해를 하는 부분이 어려웠다.

처음에는 동쪽/서쪽가는 자동차의 마주치는것에만 초점을 두어 잘못 접근하였는데, 후에 곰곰히 생각해보며 문제를 파악하였다.

우선 문제 자체를 파악해보자면 동쪽으로 가는 자동차가 있고 서쪽으로 가는 자동차가 들어올때 각 0과 1의 데이터를 가진다.

우선 총 서쪽으로 가는 자동차의 수를 1의 갯수만큼 reduce를 통해 도출해낸다. 그러면 동쪽으로 가는 자동차가 나올때마다 몇개의 서쪽으로 가는 자동차를 거쳤는지 알 수 있다.

그다음 총 결과값을 resultSum으로 선언해준다.

총 들어온 어레이의 인덱스로 접근해 반복문을 돌린다.

만약 데이터가 0 즉 동쪽으로 가는 자동차라면 이후 서쪽으로 가는 자동차를 다 만나게 되니까 sumOfGivenData의 값을 더해준다.

만약 서쪽으로 가는 자동차가 나온다면 이후 동쪽으로 가는 자동차가 나와도 해당 서쪽으로 가버린 자동차는 만나지 못함으로 sumOfGivenData에서 1만큼 빼준다. (해당 자동차는 가고 없음으로..!!)

그렇게 동/서쪽 자동차에 대해 조건을 처리하여준다.

마지막으로 총 합이 1,000,000,000 이상이면 -1을 리턴해주고 아니라면 도출된 결과값을 리턴해준다.

이렇게하면 이중 반복을 돌지 않아도 해결되며 시간 복잡도 또한 아래와 같이 효율적으로 구할 수 있다.

 

[참고자료]

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

PassingCars coding task - Learn to Code - Codility