Lesson 5. Perfix Sums - GenomicRangeQuery #2 (속도 개선)

1. 속도 개선 아이디어

각 문자가 나타난 횟수를 미리 저장해둔다.

 

예를들어 S = CAGCCTA 일 때, 다음과 같이 부분 합(Prefix Sums)을 생각해 볼 수 있다.

index	문자열S	A	C	G	T
0	초기 상태	0	0	0	0
1	C	0	1	0	0
2	CA	1	1	0	0
3	CAG	1	1	1	0
4	CAGC	1	2	1	0
5	CAGCC	1	3	1	0
6	CAGCCT	1	3	1	1
8	CAGCCTA	2	3	1	1

 

P = 2, Q = 4 를 생각해보자.

S[2]까지의 부분합은 [1, 1, 0, 0] 이다.

S[4]까지의 부분합은 [1, 3, 1, 0] 이다. (초기 상태가 있기 때문에, index 5를 봐야한다.)

이제 S[4] - S[2]를 해보면, [0, 2, 1, 0] 임을 알 수 있다. 즉, S[2] ~ S[4] 구간에서 C와 G가 나타났음을 알 수 있다.

 

 

2. C++ (코드)

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {

    //부분 합 구하기
    vector<int> A(S.size() + 1, 0);
    vector<int> C(S.size() + 1, 0);
    vector<int> G(S.size() + 1, 0);
    vector<int> T(S.size() + 1, 0);

    for(size_t i = 0; i < S.size(); i++)
    {
        A[i + 1] = A[i];
        C[i + 1] = C[i];
        G[i + 1] = G[i];
        T[i + 1] = T[i];

        if(S[i] == 'A') A[i + 1]++;
        else if(S[i] == 'C') C[i + 1]++;
        else if(S[i] == 'G') G[i + 1]++;
        else T[i]++;

    }

    //가장 작은 문자 찾기
    vector<int> result;
    for(size_t M = 0; M < P.size(); M++)
    {
        int start = P[M];
        int end = Q[M];

        if(A[end + 1] - A[start] > 0) result.emplace_back(1);
        else if(C[end + 1] - C[start] > 0) result.emplace_back(2);
        else if(G[end + 1] - G[start] > 0) result.emplace_back(3);
        else result.emplace_back(4);
    }

    return result;
}

 

 

3. 결과