Prefix Sums - PassingCars

처음에 문제를 이해못해서 한참 고민했다.

결론은 뭐 차가오른쪽이고 왼쪽이고 다 상관없고 그냥 P < Q이 조건에 맞는 쌍의 개수를 구하면된다.

처음에는 for를 2개만들어야 되나했는데 보통 문제에서 for를 중첩으로 쓴다거나 2개를 돌린다거나 하면 100퍼 성능에서 통과못하기때문에 무조건 1루프에 다 끝내는 방법을 생각해야됨

P < Q 이 조건을 만족하는 짝을 만들면 되기때문에 P를 계속 더해주면 짝대로 계속 증가하는거랑 똑같음

int answer = 0;
int P = 0;
for(int i = 0; i < A.length; i++){
    if(A[i] == 1){
        answer += P;
    } else {
        P++;
    }
}
return answer;

이렇게 했는데 100퍼가 안됨. 걍 내가 문제를 재대로 안 읽은 거였음

The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.

조건이 하나 더 있었는데

int answer = 0;
int P = 0;
for(int i = 0; i < A.length; i++){
    if(A[i] == 1){
        answer += P;
    } else {
        P++;
    }
}
if(answer > 1000000000) answer = -1;
return answer;

그래서 추가했는데 큰 범위에서는 통과를 못했다.

int answer = 0;
int P = 0;
for(int i = 0; i < A.length; i++){
    if(A[i] == 1){
        answer += P;
    } else {
        P++;
    }
    if(answer > 1000000000) {
         answer = -1;
         break;
    }
}
return answer;

그래서 루프안에 체크해주는걸 넣어서 조건만족하면 중간에 중단되게 만들었더니 통과됨~

재대로 안보고 느려서 그런줄알았는데 큰범위는 overflow로 음수로 값이 나와서 그런거였음

int answer = 0;
int P = 0;
for(int i = 0; i < A.length; i++){
    if(A[i] == 1){
        answer += P;
    } else {
        P++;
    }
}
if(answer > 1000000000 || answer < 0) answer = -1;
return answer;

그래서 이렇게 해도 통과됨.

순회시간을 줄일수있으니까 루프에서 중단되게 하는방법이 더 좋은거같음.