[codility] Prefix Sums - PassingCars

문제

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.Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

문제 해설

A 배열이 0 1 1 0 1 -> 자동차의 쌍이 (0,1), (0,2), (0,4), (3,4) 4를 리턴

구현 해설

첫번째 : 하나씩 짝을 지어주려고 접근 -> 시간복잡도 이슈 발생

두번째 : 카운팅으로 변경했으나 filter에서 시간복잡도 이슈 발생

세번째 : [0, 1, 0, 1, 1] 인경우 0이 하나인경우에 1을 만나면 1증가, 0이 두개인경우에 1을 만나면 2증가로 해결 

- 문제풀기 전에 고민을 더 해보고 접근해야겠다는 생각이 듦

 

https://app.codility.com/demo/results/trainingFAJWSU-49D/

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    
    var arr: [(Int,Int)] = []
    for (index, _) in A.enumerated() {
        if A[index] == 0 {
            for i in index..<A.count {
                if A[i] == 1 {
                    arr.append((0, 1))
                }
            }
        }
    }
    
    if arr.count > 1000000000 {
        return -1
    }
    
    return arr.count
}

 

시간복잡도 이슈

https://app.codility.com/demo/results/trainingTU9SBU-V6J/

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    var resultCount = 0
    for (index, _) in A.enumerated() {
        if A[index] == 0 {
            let size = A[index...A.count-1].filter { $0 == 1 }
            resultCount += size.count
        }
    }
    return resultCount
}

 

https://app.codility.com/demo/results/trainingPNMNE5-H38/

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    var result = 0
    var sum = 0
    
    for (index, _) in A.enumerated() {
        if A[index] == 0 {
            sum += 1
        } else {
            result += sum
        }
    }
    
    if result > 1000000000 {
        return -1
    }
    
    return result
}