Lesson 3: GenomicRangeQuery (Genomic Range Query)

https://codility.com/programmers/lessons/3
Lesson 3:  GenomicRangeQueryの解答がこちらになります。

また、別の「running total」の問題です。

やり方としては、一度文字列Sをスキャンしますが、その間に、ある位置でそれまでに出現したACGTのそれぞれの数を数えておきます。

そうした場合、ある位置pでACGTのそれぞれの今までのトータルが[4,2,3,1]であり、ある位置qでは[4,5,5,1](p <= qとします）、AとTのカウントは増えてないので、pとqの間には存在しないと言えます。逆にCとGのカウントは増えていますから、存在したと言えます。

下のサンプルのように、このやり方で１００％のスコアがでますね。

--------------------------------
SOLUTION
--------------------------------
struct Results solution(char *S, int P[], int Q[], int M) 
{
    typedef struct ACGT {
        int a;
        int c;
        int g;
        int t;
    } ACGT;
    
    int N = strlen(S);
    ACGT* acgt = calloc(sizeof(ACGT), (N + 1));
    
    int i;
    int a = 0;
    int c = 0;
    int g = 0;
    int t = 0;

    //count the numbers of ACGT. 
    for (i = 0; i < N; i++){
        switch(S[i]){
            case 'A':
                a++;
                break;
            case 'C':
                c++;
                break;
            case 'G':
                g++;
                break;
            case 'T':
                t++;
                break;
            default:
                exit(-1);
        }
        //we leave acgt[0] untouched (filled with zero)
        //so that we can simplify the next step.
        acgt[i + 1].a = a;
        acgt[i + 1].c = c;
        acgt[i + 1].g = g;
        acgt[i + 1].t = t;
    }
    
    
    struct Results result;
    
    result.A = calloc(sizeof(int), M);
    result.M = M;
    
    for (i = 0; i < M; i++){
        ACGT s = acgt[P[i]];
        ACGT e = acgt[Q[i] + 1];
        if (e.a - s.a > 0){
            result.A[i] = 1;
        }
        else if (e.c - s.c > 0){
            result.A[i] = 2;
        }
        else if (e.g - s.g > 0){
            result.A[i] = 3;
        }
        else {
            result.A[i] = 4;
        }
    }
    
    
    free(acgt);
    
    return result;
}