[Codility] Lesson 5 : PassingCars - JAVA

문제

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

 

문제 해설

solution(int[] A)는 N개의 정수를 가지고 있고, N의 범위는 1 ~ 100,000이다.
배열 A의 요소는 0 또는 1만 가질 수 있다.
숫자 0은 동쪽으로 이동하는 자동차를 의미하고,
숫자 1은 서쪽으로 이동하는 자동차를 의미한다.

이 떄 서로 마주칠 수 있는 자동차의 쌍을 (P, Q)로 표현하며,
P는 동쪽으로 이동하는 차를, Q는 서쪽으로 이동하는 차를 의미한다. (0 ≤ P < Q < N)

예를 들어 배열 A는 다음과 같다고 한다.
        A[0] = 0
        A[1] = 1
        A[2] = 0
        A[3] = 1
        A[4] = 1

이 때 A[0]과 A[2]는 동쪽으로 이동하는 자동차를, A[1], A[3], A[4]는 서쪽으로 이동하는 자동차를 말하며,
동쪽으로 이동하는 A[0]는 서쪽으로 이동하는 A[1], A[3],  A[4]와 마주칠 수 있다.
이를 (P, Q)로 표현하면 (0, 1), (0, 3), (0,4)가 된다.
즉, P는 동쪽으로 이동하는 자동차의 인덱스번호, Q는 서쪽으로 이동하는 자동차의 인덱스 번호이다.

A[0]부터 A[3]까지 위 과정을 통해 비교하면 (0, 1), (0, 3), (0, 4), (2, 3), (2, 4)가 되며,
총 5번 자동차 끼리 교차할 수 있다.
이 때 교차한 횟수를 반환해주면 된다.

단, 교차한 횟수가 1,000,000,000를 초과할 경우 -1을 반환해주면 된다.

 

풀이 - 1

class Solution {
    public int solution(int[] A) {
        int count = 0;
        for(int i=0; i<A.length; i++) {
            if(A[i] == 0) {
                for(int j=i+1; j<A.length; j++) {
                    if(A[j] == 1) count++;
                }
            }
        }
        return count;
    }
}

 

'풀이 - 1'에 대한 회고

 

일단 첫 번째 방법! 이중 반복문 사용!

첫 번째 반복문에서 요소가 0인 경우 두 번째 반복문을 통해

현재 0의 위치(인덱스)보다 크고 숫자가 1인 요소들을 찾는다.

이 과정을 거치면 정확하게 몇 번 교차하는지 확인할 수 있다.

다만 퍼포먼스가 안나온다.

 

 

정확하지만 성능이 나오지 않는 알고리즘.

 

 

결국 예상대로 O(n*n)의 시간복잡도가 나왔다.

다른 좋은 방법이 있을거야!

조금 더 고민해보고 문제를 다시 풀어봐야겠다!

 

풀이 - 2

class Solution {
    public int solution(int[] A) {
        int zeroCount = 0;
        int count = 0;
        for(int subA : A) {
            if(subA == 0) zeroCount++;
            else count += zeroCount;
        }
        return (count > 1000000000) ? -1 : count;
    }
}

 

'풀이 - 2'에 대한 회고

 

'풀이 - 1'은... 진짜 생각하기 싫었나보다.

두 번째 방법은 반복문을 돌며 숫자 0을 만나면 zeroCount를 1 증가시킨다.

그리고 숫자 1을 만나면 count에 zeroCount만큼 증가시켜준다.

 

조금 더 자세히 알아보면

 

A[0]	A[1]	A[2]	A[3]	A[4]
0	1	0	1	1

 

A[0]의 값은 0이기 때문에 zeroCount++             →     zeroCount = 1, count = 0
A[1]의 값은 1이기 때문에 count+=zeroCount    →     zeroCount = 1, count = 1
A[2]의 값은 0이기 때문에 zeroCount++             →     zeroCount = 2, count = 1
    ※ A[2]는 A[1]을 만날 수 없다.
A[3]의 값은 1이기 때문에 count+=zeroCount    →     zeroCount = 2, count = 3
A[4]의 값은 1이기 때문에 count+=zeroCount    →     zeroCount = 2, count = 5

 

그 결과...

 

 

퍼포먼스가 80%로 증가했다. 그러나 아직 100%가 아니다.

다른 사람들이 어떻게 풀이했는지 확인해봐야지!

아! 그리고 시간복잡도 또한 O(n)이 나왔다.

 

 

다른 사람의 풀이

class Solution {
    public int solution(int[] A) {
        int zeroCount = 0;
        int count = 0;
        for(int subA : A) {
            if(subA == 0) zeroCount++;
            else count += zeroCount;
            if(count > 1000000000) return -1;
        }
        return count;
    }
}

 

'다른 사람의 풀이'를 통한 회고

 

나는 바보였어...

다른 사람의 풀이를 보고 뭐가 누락되었는지 바로 알았다.

어차피 교차한 횟수가 1,000,000,000을 초과하면 -1을 반환해주면 되는데

반복문을 다 수행하고 교차 횟수가 초과했는지 비교할 필요가 없다!

그냥 반복문에서 교차 횟수가 초과하면 바로 -1을 반환하면 된다.

 

저 코드 한 줄의 차이가 퍼포먼스를 망쳐놨다니.

왜 저렇게 생각하지 않고 그냥 막 코딩을 했지?

일단 원인을 알았으니 다음에 코딩을 할 때 주의해야지!