[C++ 풀이] Codility - Lessons 5, (Prefix Sums) GenomicRangeQuery

이 문제는 Codility 사이트에서 확인하고 문제를 풀 수 있습니다.

https://www.codility.com/

 

 

문제.

 

 

설명

 

N 길이만큼의 랜덤한 문자열이 주어 집니다. (N의 크기는 1 ~ 100,000)

문자열의 구성은 A, C, G, T 이렇게 4가지 입니다.

중간에 스페이스바는 없으며 위 4개의 알파벳 조합의 문자열이 주어집니다.

 

알파벳은 다음과 같은 점수를 갖고 있습니다.

A = 1,

C = 2,

G = 3,

T = 4

 

위 문제는 주어진 범위 내에 4가지 알파벳으로 구성된 문자열 중 점수가 가장 작은 알파벳을 찾아내는 문제 입니다.

 

범위는 P와 Q로 주어 집니다.

P와 Q 범위는 1 ~ 50,000이며(P[0] ~ P[49999])

각 요소의 값은 0 ~ N-1 까지 있을 수 있습니다.

P[0] = 1, P[1] = 99,999 .....

 

 

범위를 찾는 방법은 간단 합니다.

 

문제에 나와 있는 예시 처럼 문자열이 다음과 같이 주어진다고 가정 했을때 범위를 구해보겠습니다.

S = CAGCCTA

P[2] =

Q[2] =

 

이 주어졌을 때,

P[0] = 2,     Q[0] = 4    이므로

 

C  A  G  C  C  T  A

0  1   2  3  4  5  6

 

G C C 중에 점수가 작은걸 찾으면 됩니다. 

답은 C이니 2가 답으로 넣어지게 됩니다.

 

이 방식대로 

P[1] = 5,    Q[1] = 5

P[2] = 0,    Q[6] = 6

 

을 찾으면 다음과 같은 숫자가 나오게 됩니다.

[2, 4, 1]

 

위 점수를 해당 문제의 반환 값에 맞게(배열이든 vector든) 점수를 입력해 return해 주면 됩니다.

 

 

 

 

 

 

1차 결과

 

https://app.codility.com/demo/results/trainingU9BTRR-M4R/

 

#include <algorithm>

using namespace std;
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
    // write your code in C++14 (g++ 6.2.0)
    int A = 0, C = 0, G = 0, T = 0;
    vector<int> v;
    
    for(int i = 0; i < P.size(); i++){
        for_each(&(S.at(P[i])), &(S.at(Q[i])) + 1,[&](auto& s){
            if(s == 'A')
                A++;
            else if(s == 'C')
                C++;
            else if(s == 'G')
                G++;
            else
                T++;
        });
        
        if(A != 0)
            v.push_back(1);
        else if(C != 0)
            v.push_back(2);
        else if(G != 0)
            v.push_back(3);
        else
            v.push_back(4);
            
        A = C = G = T = 0;
    }
    
    return v;
    
}
​

 

위 문제는 시간 복잡도 N + Q를 보는 문제 입니다.

즉 2중 for문은 안됩니다.....

위 답은 N * Q로 퍼모먼스 점수가 0점이 나와버렸습니다.....

 

 

 

 

그렇게 1주일정도 고민하다가.................

 

그만 문제에 대해 잊어버리게 됐습니다......

 

정확히는 하기 싫어져서.................................

 

 

그리고 오늘..... 해답을 보고 풀었습니다.

 

해답을 봤을 때 "와.... 이런 방법이 있내..." 라고 속으로 감탄하고 

저는 정말 좁바...압이 아니라 실력이 없다는걸 새삼 다시 느끼게 됐습니다.

 

그래도 해답을 이해하고 푼걸로 만족해야 겠습니다.....

 

 

 

2차 결과

 

 

https://app.codility.com/demo/results/trainingS3AANS-5YU/

 

 

 

// you can use includes, for example:
#include <algorithm>
#include <cstring>
using namespace std;
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
    // write your code in C++14 (g++ 6.2.0)
    int max_index = S.size() + 1;
    int *A = new int[max_index];
    int *C = new int[max_index];
    int *G = new int[max_index];
    int i = 1;
    vector<int> v;
    
    memset(A, 0, sizeof(int) * (max_index));
    memset(C, 0, sizeof(int) * (max_index));
    memset(G, 0, sizeof(int) * (max_index));
    
    for_each(&(S.at(0)), &(S.at(S.size() - 1)) + 1, [&](auto& s){
        if(s == 'A')
            A[i]++;
        else if(s == 'C')
            C[i]++;
        else if(s == 'G')
            G[i]++;
            
        A[i] += A[i - 1];
        C[i] += C[i - 1];
        G[i] += G[i - 1];
        i++;
    });

    for(int i = 0; i < P.size(); i++){
        int S_index = P[i];
        int E_index = Q[i] + 1;
        
        if(S_index == E_index){
            switch(S.at(S_index)){
                case 'A':
                    v.push_back(1);
                    break;
                case 'C':
                    v.push_back(2);
                    break;
                case 'G':
                    v.push_back(3);
                    break;
                case 'T':
                    v.push_back(4);
            }
        }
        else if(A[S_index] != A[E_index])
            v.push_back(1);
        else if(C[S_index] != C[E_index])
            v.push_back(2);
        else if(G[S_index] != G[E_index])
            v.push_back(3);
        else
            v.push_back(4);
    }
    
    return v;

}
​

 

 

문제 풀이

 

 

위 문제는 해당 알파벳이 나올 때 마다 카운터를 세서 범위의 첫 범위와 끝 범위만 보고 카운터 값이 변경이 됐는지 안됐는지만 판단하고 

변경이 됐으면 해당 알파벳 점수를 호출, 변경이 안됐으면 다음 알파뱃 검사.....

 

이런식으로 만들었습니다.

 

글로만 읽으면 이해하기 어려우니 상세히 설명하겠습니다.

 

C A G C C T A를 보고 카운터를 세보겠습니다.

 

A같은 경우 다음과 같이 카운터를 셉니다.

 

1회전 : 0, 0, 0, 0, 0, 0, 0

2회전 : 0, 1, 0, 0, 0, 0, 0

3회전 : 0, 1, 1, 0, 0, 0, 0

4회전 : 0, 1, 1, 1, 0, 0, 0

5회전 : 0, 1, 1, 1, 1, 0, 0

6회전 : 0, 1, 1, 1, 1, 1, 0

7회전 : 0, 1, 1, 1, 1, 1, 2

 

즉, 2회전때 A가 나왔음으로 A배열의 카운터 1개를 올려줍니다.

그 뒤 변화가 없다면 올린 값 카운터를 그대로 다음 인덱스 값에 넣어 줍니다.

이렇게 되버리면 2회전을 마지막으로 6회전 까지는 알파벳 A는 안나왔다는 뜻이 되고

만약 P[3],    Q[5]의 범위가 주어진다고 가정한다면 변화된 값이 없기 때문에.

 

즉, 검색할 범위 내에 A의 카운터가 이뤄져야 하는데 이 카운터가 이뤄지지 않았기 때문에 A는 현재 범위에 없다고 판단!!

좀 더 자세히 설명 하자면....

1회전과 2회전을 보면 0에서 1로 카운터 된걸 알 수 있습니다.

그 결과 우리는 2회전에 A가 등장했다는걸 알 수 있게 됩니다.

따라서 카운터된 시점인 A[1]이 포함이 되면 해당 범위 안에 A알파벳이 있다는걸 확인할 수 있습니다.

반면 3회전부터 6회전 까지는 1로 쭉 이어지고 있습니다. 

이는 3회전 전 1회전 혹은 2회전 때에 A알파벳이 나왔지만 그 후론 안나왔다는걸 뜻합니다.

때문에 A[2] ~ A[5]범위엔 알파벳 'A'가 없다는 결론이 나옵니다.

하지만 7회전에선 알파벳 'A'가 나옴으로 써 카운터가 1에서 2로 바뀌게 됩니다.

때문에 A[2] ~ A[6]범위 내에선 A가 있다는 결론이 나오게 됩니다.

즉, 찾을 범위의 첫 번째 값인 "P[0] = 2"와 마지막 값인 "Q[0] = 4" 범위에선

A의 카운터 배열 안에 변화된 카운터가 없음으로, 해당 범위엔 A가 없다는 결론이 나오게 됩니다.

 

결국 카운터가 되는 시점은 해당 범위 내의 A의 값이 다른 경우에 카운터가 증가됐다는 뜻이고,

찾을 첫 번째 인덱스 값과 마지막 인덱스 값이 같은지 다른지만 알면 

우리는 쉽게 해당 범위에 알파벳이 있는지 없는지 알게 됩니다.

 

 

 

이정도 설명이면 충분하다고 생각합니다......

 

더 설명하는 것도 힘들고.... 이걸 보시는 분들에게도 더 이상의 도움은 안될 것이라 판단되어

여기까지만 하겠습니다. :)

 

이해가 안가시면 또 읽고 코드 짜고 해보시면 아마 되실겁니다???