[Codility] GenomicRangeQuery c++

• 문제

DNA서열은 A, C, G, T 로 구성 되어 있고   1, 2, 3, 4 로 표현된다.

string으로 DNA 서열이 주어진다.

 

 

배열 P ,Q 의 K번째 값으로

string s의 K(P) ~ K(Q)번째 원소들 중 서열이 제일 먼저인  DNA 인덱스를 저장한다.

 

• 문제 해결

2중 for문을 사용하면 시간 복잡도 테스트를 통과하지 못해서

2중 for문을 사용하지 않게 코드를 짜보았다.

// you can use includes, for example:
#include <algorithm>

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
   vector<int> result;
	for (int i = 0; i < P.size(); i++) {

		int index = Q[i] - P[i];
		string tmp("");
		if (index != 0)  tmp = S.substr(P[i], index+1);
		else
			tmp.push_back(S[P[i]]);

		sort(tmp.begin(), tmp.end());

		int nucle = 0;
		if ('A' == tmp[0])   nucle = 1;
		else if ('C' == tmp[0])  nucle = 2;
		else if ('G' == tmp[0])  nucle = 3;
		else {
			nucle = 4;
		}
		result.push_back(nucle);
	}
	return result;
}

후.. 시간 복잡도를 더 줄여야한다.

#include <algorithm>

bool myCompare(pair<int, int> a, pair<int, int> b){
    if(a.first == b.first){
        return a.second < b.second;
    }
    else{
        return a.first < b.first;
    }
}

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
    vector<int> result;
    vector<pair<int, int>> v;
    for(int i = 0; i < S.size(); i++){
        int nCh = 0;
        if('A' == S[i]){
            nCh = 1;
        }
        else if('C' == S[i]){
            nCh = 2;
        }
        else if('G' == S[i]){
            nCh = 3;
        }
        else{
            nCh = 4;
        }
        v.push_back(make_pair(nCh, i));
    }

    sort(v.begin(), v.end(), myCompare);

    for(int i = 0; i < P.size(); i++){
        for(int j = 0; j < v.size(); j++){
            if(P[i] <= v[j].second && v[j].second <= Q[i]){
                result.push_back(v[j].first);
                break;
            }
        }
    }
    return result;
}