[Codility] PassingCars (Java)

https://app.codility.com/c/run/trainingSEY3MV-T6R/

Codility

문제는 쉬운데 이를 어찌 효율적으로 짤것인가..

당연히 2중 포문 돌리는 순간 시간초과로 난리가 났다.

 

Map을 이용해서 

0 0

1 1

2 1

3 2

4 3

으로 해당 인덱스까지 나온 1의 갯수를 구해주었다. 

 

마지막 조건문이 P < Q 이기 때문에 (2,1)인경우를 빼주기 위해서 총 count된 1의 갯수에서 내가 거쳐왔던 이전의 1의 갯수를 빼준다. (말로 하니깐 이상한데 이런방식으로 했다. )

public class PassingCars {
    public int solution(int[] A) {
        int count = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < A.length; i++) {
            if (A[i] == 1)
                count++;
            map.put(i, count);
        }
        int result = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] == 0) {
                result = result + (count - map.get(i));
                if (result > 1000000000) {
                    return -1;
                }
            }
        }
        return result;
    }
}

 

사람들 코드보니 0에서 count하고 1일때 더하는 방식으로 굉장히 간단하게 짰던데 내머리론 아직 그 코드가 이해가지 않는다. ㅠㅠ