[Codility] Lesson5 GenomicRangeQuery

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

GenomicRangeQuery coding task - Learn to Code - Codility

풀이

문제를 간단히 설명하면, A,C,G,T 만으로 이루어진 문자열 S 에서 특정 범위 내에 존재하는 가장 작은 문자를 구하면 된다. ( A = 1, C = 2, G = 3, T = 4 로 반환)

 

문제를 푸는 것 자체는 그렇게 어렵지 않은데.. 시간 복잡도 해결이 어려웠다.

숫자의 최대범위가 매우 크다.

문자열 S의 최대길이 N은 100,000 이고, 

특정 범위 내에 존재하는 가장 작은 문자를 구해야 하는 쿼리의 개수 M 의 최댓값은 50,000 이다.

 

최악의 경우를 생각해보면..

100,000 자리의 문자열 S의 0부터 100,000 사이의 최솟값을 50,000번 구해야 한다.

50,000 * 100,000 = 5,000,000,000 ( 50억 ) 이므로.. 1억회의 연산 당 1초가 걸린다고 가정해도 무려 50초가 걸린다..

 

따라서 해당 문제는 O(N) 의 시간복잡도로 풀이해야 한다.

 

Write an efficient algorithm for the following assumptions:

• 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.

 

처음 문제를 접했을 때, 도저히 해답이 떠오르지 않아 구글링 해서 찾은 해결방안은 아래와 같다.

유사한 유형의 문제를 만났을 때, 이러한 알고리즘을 떠올릴 수 있도록 정리해둔다.

 

1. 문자열 S 내부에 포함된 문자는 'A', 'C', 'G', 'T' 4개 뿐이므로, 각각의 문자가 특정 인덱스까지 몇개가 나타났는지를 표기할 배열을 만든다.

A[i] = 문자열 S의 i번째 인덱스까지 나타난 A의 총 갯수

2. 각 쿼리의 최소값이 P[i], 최댓값이 Q[i] 라고 할 때, A[P[i]] 값과 A[Q[i] + 1] 값이 같지 않다면.. 해당 범위 내에 A라는 알파벳이 포함되었음을 뜻한다. 

3. 2번의 논리를 활용하여 A, C, G, T 배열에서 최솟값의 인덱스와 최댓값의 인덱스에 차이가 있는지 확인하여 해당 알파벳이 나타났는지 파악한다.

 

// you can also use imports, for example:
import java.util.*;
​
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
​
class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        // write your code in Java SE 8
​
        int A[] = new int[S.length() + 1];
        int C[] = new int[S.length() + 1];
        int G[] = new int[S.length() + 1];
        int T[] = new int[S.length() + 1];
​
        int answer[] = new int[P.length];
​
        for(int i=0; i<S.length(); i++){
            switch(S.charAt(i)){
                case 'A' : A[i+1]++; break;
                case 'C' : C[i+1]++; break;
                case 'G' : G[i+1]++; break;
                case 'T' : T[i+1]++; break;
            }
            A[i+1] += A[i];
            C[i+1] += C[i];
            G[i+1] += G[i];
            T[i+1] += T[i];
        }
​
        for(int i=0; i<answer.length; i++){
            if(A[P[i]] != A[Q[i]+1]){
                answer[i] = 1;
            }else if(C[P[i]] != C[Q[i] + 1]){
                answer[i] = 2;
            }else if(G[P[i]] != G[Q[i] + 1]){
                answer[i] = 3;
            }else{
                answer[i] = 4;
            }
        }
​
        return answer;
​
    }
}