Codility:Lesson5(Prefix Sums) - PassingCars

안녕하세요~~

디벨로퍼입니다.

오늘은 Codility의 Passing Car 문제를 풀이했습니다.

 

문제풀이 하실분은 하단의 링크 참조해주세요

==========================================================================

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

PassingCars coding task - Learn to Code - Codility

==========================================================================

 

 

Passing Car

배열의 값 0은 오른쪽으로 가는 차, 1은 왼쪽으로 가는차를 의미합니다.

그래서 0, 1이 연속적으로 있다면 서로 통과하는 차량을 의미합니다.

생각한 나는 풀이가 오른쪽으로 가는 차량의 개수를 세주고 

만약 왼쪽으로 가는 차량이 있으면 서로 교차하는 차의 개수라 정답에 더해주었습니다

 

풀이는 아래와 같습니다.

 

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    unsigned long long zero_count = 0, res = 0;
    for(vector<int>::iterator iter = A.begin(); iter != A.end(); ++iter)
    {
        if(*iter == 0) zero_count++;
        else res += zero_count;
    }
    if(res > 1000000000) res = -1;
    return res;
}

 

여기서 조심해야 될 부분이 Overflow 였습니다.

정답 중 10억이 넘으면 -1 처리를 해주어야하는데 

케이스 중에 int 형의 최대 범위를 넘어가는 답이 있어 int로 변수를 정의하면 실패가 됩니다.