[Swift] 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:

class Solution { public int solution(int[] 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:

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[2]는 서쪽으로 가는 a[1]차를 마주치지 않느다.

2보다 먼저 온 서쪽으로 가는 차는 안마주친다고 보면된다.

 

해결방법은 우선 동쪽으로 가는 차가 나오면

그 다음 배열을 잘라서 서쪽으로 가는 차만 필터링한후에 카운팅을 늘리는 방식을 했다.

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)

    var answer = 0

    for i in 0..<A.count{
        if(A[i] == 0) {
            let afterArr = A.suffix(A.count-(i+1))
            let filteredArr = afterArr.filter({$0 == 1 })
            answer += filteredArr.count

            if(answer > 1000000000){return -1}
        }
    }

    return answer
}

정답은 맞췄으나 o(n ** 2) 시간 초과가 나왔다.

배열을 잘라내고 필터링 하는 과정이 시간초과를 불렀다.

 

 

그래서 해결 방법을 바꿔보았다.

 

동쪽으로 가는 차가 나오면 pCount를 1 올려준다.

그다음 서쪽으로 가는 차가 나오면 pCount 를 answer 값에 더해준다.

예로 동쪽으로 가는 차가 2개 나오고 그후에 서쪽 차가 나오면 ([0,0,1])

pCount는 2 가 되고 2만큼을 더해주면 된다.

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)

    var pCount = 0
    var answer = 0

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