codility - PassingCars 정답 및 해설

난이도 ★★☆☆☆

문제를 보시려면 여기를 클릭

문제 요약

각 0의 뒤에 나오는 1의 개수를 각각 구한다음 걔네를 다 더하기 (오버플로우나면 -1 리턴)

힌트

미리 1의 개수를 구해놓는 방법을 통해 중첩for문 제거

이하는 코드입니다. (복잡도 2n의 코드인데, 개선하면 n도 가능할겁니다)

public int solution(int[] A) {
    int firstZeroIndex = -1;
 
    for (int i = 0; i < A.length; i++) {
        if (A[i] == 0) {
            firstZeroIndex = i;
            break;
        }
    }
 
    if (firstZeroIndex == -1) {
        return 0;
    }
 
    int totalOneCount = 0;
 
    for (int i = firstZeroIndex + 1; i < A.length; i++) {
        if (A[i] == 1) {
            totalOneCount++;
        }
    }
 
    if (totalOneCount == 0) {
        return 0;
    }
 
    int result = totalOneCount;
    int lastOneCount = 0;
 
    for (int i = firstZeroIndex + 1; i < A.length; i++) {
        if (A[i] == 0) {
            result += totalOneCount - lastOneCount;
 
            if (result > 100000000 || result < 0) {
                return -1;
            }
        }
        else if (A[i] == 1) {
            lastOneCount++;
        }
    }
 
    return result;
}