[Codility] 5. PassingCars

문제 링크

PassingCars

문제 요약

주어진 배열 A의 요소는 0 혹은 1로 주어진다.
A[i]의 인덱스 번호판을 달고있는 자동차가 0일 때 동쪽으로 가는 것을 뜻하며, 1일때는 서쪽으로 간다.
서쪽으로 가는 자동차의 인덱스 번호판이 클 때, 만들어질 수 있는 pairs count를 구하라

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)

요구사항

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.

코드

A의 특정 인덱스가 0이라면 그 이후에 나온 1 값들의 총 수를 각각 다 더하면 되지만, 이중 for loop가 되므로 O(N**2)이다.

처음 0 번호판을 가진 차량이 있고, 그 다음 똑같은 번호를 가진 차량이 나온다면...
예를들어 0 1 0 1이 있다고 생각하자.
맨 처음 0이 나오고, 그 다음 1이 나오면 주어진 조건에 맞으므로 1쌍이 추가된다.
그리고 세 번째 인덱스에는 0이 나오고, 네 번째에 1이 나온다.
그럼 맨 처음 0이 나온 인덱스는 마지막에 나온 1과도 쌍을 이룰 수 있으므로 마지막에 나온 1 이전의 0의 개수까지 합해서 더한다면 쌍을 구할 수 있다.

O(N)

public func solution(_ A : inout [Int]) -> Int {
    var eastNum: Int = 0
    var sum: Int = 0

    for i in 0..<A.count {
        if(A[i] == 0) {
            eastNum += 1
        } else {
            sum = eastNum + sum
            if(sum > 1000000000) {
                return -1
            }
        }
    }
    return sum
}