codility - GenomicRangeQuery (Prefix Sums)

풀이법을 몰라서 못풀었다. 

절대 완전탐색이 아니라는 것은 자명한 사실이었고, 

단순히 인덱스 2개만으로 그 사이에 A,C,G가 포함되어있는지 

대체 어떻게 알 수 있을까 고민하고 정답을 보니 

알파벳의 누적개수를 이용해서 

인덱스 사이의 누적개수 변화를 활용해 문제를 해결하는 방식이었다.

A,C,G순서대로 해당 알파벳에서 변화를 할 경우 뒤에 것을 확인할 필요가 없다는 것

A,C,G 3개의 알파벳 모두 변화를 안하면 마지막 남은 T가 변화한다는 것

테크닉만 알면 쉬운 문제였는데 IF ELSE문 자주 안쓰고 IF IF만 쓰다보니까 엉뚱한 곳에서 실수함

    public int[] solution(String S, int[] P, int[] Q) {
        // write your code in Java SE 8
 
        System.out.println(S);
 
        int[] answer = new int[P.length];
 
        int[] A = new int[S.length() + 1];
        int[] C = new int[S.length() + 1];
        int[] G = new int[S.length() + 1];
 
        for (int i = 0; i < S.length(); i++) {
            // System.out.println(S.charAt(i));
            if (S.charAt(i) == 'A') {
                A[i + 1] = A[i] + 1;
                C[i + 1] = C[i];
                G[i + 1] = G[i];
            } else if (S.charAt(i) == 'C') {
                C[i + 1] = C[i] + 1;
                A[i + 1] = A[i];
                G[i + 1] = G[i];
            } else if (S.charAt(i) == 'G') {
                G[i + 1] = G[i] + 1;
                A[i + 1] = A[i];
                C[i + 1] = C[i];
            } else {
                A[i + 1] = A[i];
                C[i + 1] = C[i];
                G[i + 1] = G[i];
            }
 
        }
 
        for (int i = 0; i < P.length; i++) {
            int start = P[i];
            int end = Q[i] + 1;
            if (A[end] - A[start] > 0)
                answer[i] = 1;
            else if (C[end] - C[start] > 0)
                answer[i] = 2;
            else if (G[end] - G[start] > 0)
                answer[i] = 3;
            else
                answer[i] = 4;
        }
 
        return answer;
    }