Codility lesson5_2 - GenomicRangeQuery

요약

DNA 관련 문제입니다. DNA를 이루는 뉴클리오타이드 염색체 A, C, G, T가 들어 있는 문자열 S가 주어지고 이 염색체는 각각 1, 2, 3, 4와 매칭이 됩니다. 그리고 S.size() 미만의 정수가 들어 있는 P와 Q가 주어집니다. 문자열 S에서 P와 Q 사이에 있는 염색체중 가장 작은 값을 가지는 정수를 구해서 각 케이스마다 정수를 벡터에 차례로 모아서 반환하면 됩니다.

예를 들어 S = "CAGCCTA"이고 P[0] =2, P[1] = 5, P[2] = 0 / Q[0] = 4, Q[1] = 5, Q[2] = 6라고하면

P[0] ~ Q[0]는 2~4사이의 문자열인 GCC인데요 여기서 G는 3 C는 2이기때문에 2가 반환이 되어야합니다.

P[1] ~ Q[1]은 5~5인 T는 4입니다.

 

아이디어 

1. 문자열 A C G T로 이루어져 있지만 반환값은 1 2 3 4와 같은 정수이기 때문에 파싱이 먼저 이루어져야 함

2. 파싱된 값을 PQ문자열 사이값이 나타날때 해당 범위만 정렬하여 가장 작은 값을 반환하면 됨

 

코드

#include<algorithm>
int DNA_Check(string s)
{
	vector<int>ACGT;

	for (auto it : s)
	{
		if (it == 'A')
			ACGT.push_back(1);
		else if (it == 'C')
			ACGT.push_back(2);
		else if (it == 'G')
			ACGT.push_back(3);
		else if (it == 'T')
			ACGT.push_back(4);
	}
	sort(ACGT.begin(), ACGT.end());
	return ACGT[0];
}
vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
	// write your code in C++14 (g++ 6.2.0)
	string s;
	vector<int>sol;
	for (int i = 0;i<P.size();i++)
	{
		s = S.substr(P[i], Q[i] - P[i]+1);
		sol.push_back(DNA_Check(s));
	}
	return sol;
}

결과는

네 퍼포먼스에서 O(N*M)으로 박살나버렸네요....

PQ 범위를 확인할때마다 정렬을 하기때문에 이렇게 되버린것 같네요...

그렇다면 정렬을 한번만 할 경우에 O(N+M)정도 나올 수 있을 것 같네요

코드

#include<algorithm>
vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
	// write your code in C++14 (g++ 6.2.0)
	vector<pair<int, int>>ACGT;
	int cnt = 0;
	vector<int>sol;
	for (auto element : S)
	{
		if (element == 'A')
			ACGT.push_back(make_pair(1, cnt));
		else if (element == 'C')
			ACGT.push_back(make_pair(2, cnt));
		else if (element == 'G')
			ACGT.push_back(make_pair(3, cnt));
		else if (element == 'T')
			ACGT.push_back(make_pair(4, cnt));
		cnt++;
	}
	sort(ACGT.begin(), ACGT.end());
	for (int i = 0; i < P.size(); i++)
	{
		for (int j = 0; j < ACGT.size(); j++)
		{
			if (P[i] <= ACGT[j].second && Q[i] >= ACGT[j].second)
			{
				sol.push_back(ACGT[j].first);
				break;
			}
		}

	}
	return sol;
}

기존의 코드에서는 파싱한 데이터만 벡터에 저장을 했었는데요. 수정된 코드에서는 위치와 함께 pair로 저장했습니다.

그 다음 정렬을 하게되면 first인 염기가 오름차순으로 정렬이 되기 때문에 ACGT의 변환되기전 위치정보를 담고있는 second를 앞쪽 배열부터 P와 Q사이에 포함이 되는지만 확인하게 되면 이후의 염기를 비교할 필요 없이 가장 작은 값을 가져갈 수 있습니다.

 

문제에서 반환값이 정수형이 되어야하기때문에 가장먼저 파싱을 해야한다는 것을 판단하고 그 데이터를 sort하는 방향으로  풀이를 해 나간것이 도움이 많이 되었던것 같네요.