GenomicRangeQuery (Codility)

문제

A, C, G, T는 순서대로 1, 2, 3, 4 값이다. 즉 A < C < G < T이다. A, C, G, T를 입력한 문자열 S와 탐색할 범위 P[i] ~ Q[i] 가 주어진다. 탐색 범위에 들어있는 알파뱃 중 가장 값이 작은 것을 컨테이너에 담아 출력하면 되는 문제이다.

 

예를 들어 CAGCCTA를 S로 입력받았고, P와 Q는 다음과 같이 입력되었다고 가정하자.

P[0] = 2    Q[0] = 4
P[1] = 5    Q[1] = 5
P[2] = 0    Q[2] = 6

i가 0일때 범위는 2 ~ 4번째 까지이다. 2번째 인덱스 G부터 4번째 인덱스 C까지 범위에서 가장 작은 알파뱃은 C이므로 정답은 2이다.

 

i가 1일때 범위는 5번째이므로, 5번째 알파뱃 T가 가장 작으므로 정답은 4이다.

 

i가 2일때 범위는 0 ~ 6번째 까지이다. 0번째 인덱스 C부터 6번째 인덱스 A까지 범위에서 가장 작은 알파뱃은 A이므로 정답은 1이다.

 

결과적으로 출력해야 할 컨테이너 값은 {2, 4, 1}이 된다.

 

해결 방법

문제 자체는 어렵지 않다. 대부분 정확도는 100퍼센트가 나올 것이다. 하지만 효율성은 100퍼센트를 만들기가 힘든 문제였다.

 

시간 복잡도가 O(N + M)가 되지 않는다면 100퍼센트로 통과가 되지 않는다. 그러므로 범위만큼 각각 검사하는 방법은 쓸 수가 없다.

 

해결 방법은 A, C, G, T의 개수를 담을 테이블을 만들어 S의 모든 인덱스 위치에서의 개수를 테이블에 담아 그 테이블을 컨테이너에 담아 기록하는 것으로 시작한다.

 

CAGCCTA를 예로 들면 다음과 같다.

초기 테이블 : [0, 0, 0, 0]
초기 기록 컨테이너 : [[0, 0, 0, 0]] (1개)

C(인덱스 0)
테이블 : [0, 1, 0, 0]
기록 컨테이너 : [[0, 0, 0, 0], [0, 1, 0, 0]] (2개)

A(인덱스 1)
테이블 : [1, 1, 0, 0]
기록 컨테이너 : [[0, 0, 0, 0], [0, 1, 0, 0], [1, 1, 0, 0]] (3개)

(부분생략...)

A(인덱스 6)
테이블 : [2, 3, 1, 1]
기록 컨테이너 : [[0, 0, 0, 0], [0, 1, 0, 0], [1, 1, 0, 0], ...., [2, 3, 1, 1]] (8개)

이제 이 컨테이너에서 2 ~ 6인덱스 범위에서 가장 작은 알파뱃이 무엇인지 구하려고 한다. 그러면 (6 + 1)번째 기록된 테이블과 2번째 기록된 테이블의 개수들을 빼주면 다음과 같다. (6 + 1번째 테이블에 접근하는 이유는 앞서 초기화된 기록 컨테이너에 [0, 0, 0, 0]이 이미 들어있기 때문이다)

(6 + 1번째 테이블) - (2번째 테이블) = [2, 3, 1, 1] - [0, 1, 0, 0] = [2, 2, 1, 1]

범위 내에 가장 작은 A 알파뱃이 2개 포함되어 있으므로 A값인 1이 정답이 된다.

 

코드는 다음과 같다.

#include <map>

vector<int> solution(string& S, vector<int>& P, vector<int>& Q)
{
	vector<int> table(4, 0); // 초기 개수 테이블 설정
	vector<int> result; 
	vector<vector<int>> record; // 테이블을 기록할 컨테이너 설정
	record.push_back({ 0, 0, 0, 0 }); // 컨테이너 초기화
	map<char, int> info; // 각 알파뱃의 값들을 담을 컨테이너
	info['A'] = 1; info['C'] = 2; info['G'] = 3; info['T'] = 4;
	// S의 정보에 맞춰 알맞은 개수 테이블을 컨테이너에 넣는다. 
	for (int i = 0; i < S.size(); ++i)
	{
		table[info[S[i]] - 1]++;
		record.push_back(table);
	}
	for (int i = 0; i < P.size(); ++i)
	{
		// 기록한 테이블 정보를 토대로 가장 작은 알파뱃 부터
		// 범위 만큼 존재하는 개수를 알아낸다.
		for (int j = 0; j < 4; ++j)
		{
			int num = record[Q[i] + 1][j] - record[P[i]][j];
			if (num > 0)
			{
				// 알파뱃이 범위내에 존재한다면 값을 컨테이너에 담는다.
				result.push_back(j + 1);
				break;
			}
		}
	}
	return result;
}