Lesson5. Prefix Sums - GenomicRangeQuery

GenomicRangeQuery - Find the minimal nucleotide from a range of sequence DNA.

https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/

문제요약

nucleotide인 문자 A,C,G,T로 구성된 문자열로 표현되는 DNA sequence가 있고, 각각의 impact factor는 1,2,3,4. 주어지는 query들에 대한 가장 작은 impact factor를 계산. query는 P, Q로 주어지고 각 index별로 DNA의 범위를 의미한다. DNA sequence의 P[K] ~ Q[K]의 범위에서 가장 작은 impact factor를 찾아라.

쉽게 정리하면, 문자열에서 특정 범위가 주어질 때, 그 범위에 등장하는 가장 작은 문자를 찾는다.

Assume that:

N is an integer within the range [1..100,000];

M is an integer within the range [1..50,000];

each element of arrays P, Q is an integer within the range [0..N − 1];

P[K] ≤ Q[K], where 0 ≤ K < M;

string S consists only of upper-case English letters A, C, G, T.

Complexity:

expected worst-case time complexity is O(N+M);

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

풀이

문제 자체는 어렵지 않으나 시간 복잡도를 만족시키는게 중요한 문제로 주로 계산량이 많아서 오래 걸리는 경우는 미리 계산해 놓거나 이전 값을 사용하거나 하는 방법등으로 줄여나가야 한다. O(N+M)이라는 것을 보면 O(M)은 입력 query에 대한 시간이므로 실제 O(N)을 통해 사전 계산이 필요하다는 것을 추측할 수도 있다. 이 문제의 경우는 앞 문제와 유사하게 구할 수 있다. Q[K]까지 나온 문자의 수에서 P[K]까지 나온 문자의 수를 빼주면 P[K]~Q[K]에 해당 문자가 등장했는지를 알 수 있다. 이렇게 등장한 문자들 중 가장 작은 값을 찾으면 된다. 이를 위해서는 [0,..,N-1]까지 해당 문자의 등장 횟수가 필요하고 이것이 사전에 계산이 필요한 부분이다. 문자열 길이 N에 대해 각 문자 A,C,G,T에 대해서 등장횟수를 우선 계산하는데 O(N)이 소요되고, 이후 query에 대해 문자를 찾는데는 상수시간이므로 O(M)이 소요된다.