PassingCars

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

PassingCars coding task - Learn to Code - Codility

 

한 방향(동 또는 서)으로 움직이는 차들이 서로 교차하는 횟수를 구하는 문제.

 

같은 방향으로 움직이는 차는 교차할 일이 없으므로, 결국 서로 다른 방향으로 움직이는 차를 카운팅 해주면 된다.

 

A[0]이 만나는 차는 A[1], A[3], A[4]

A[2]가 만나는 차는 A[3], A[4]

 

결국 자기보다 왼쪽에 있는 차들 중 반대방향으로 움직이는 차들을 카운트하면 된다.

 

합을 저장하는 배열을 만들고, 배열을 sum하면 되긴 하지만, 굳이 배열없이도 처리 가능하다.

 

class Solution {
    public int solution(int[] A) {
        int max = 1000000000;

		// 교차하는 횟수
        int answer = 0;
        
        // 교차하는 차량
        int cnt = 0;
        
        for (int i = 0; i < A.length; i++) {
            if (A[i] == 0) cnt++;
            else {
                answer += cnt;
            }
            if (answer > max) return -1;
        }

        return answer;
    }
}