[Codility] Lesson 5 : GenomicRangeQuery - JAVA

문제

A DNA sequence can be represented as a string consisting of the letters A, C, G and T, which correspond to the types of successive nucleotides in the sequence. Each nucleotide has an impact factor, which is an integer. Nucleotides of types A, C, G and T have impact factors of 1, 2, 3 and 4, respectively. You are going to answer several queries of the form: What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?
 
The DNA sequence is given as a non-empty string S = S[0]S[1]...S[N-1] consisting of N characters. There are M queries, which are given in non-empty arrays P and Q, each consisting of M integers. The K-th query (0 ≤ K < M) requires you to find the minimal impact factor of nucleotides contained in the DNA sequence between positions P[K] and Q[K] (inclusive).
 
For example, consider string S = CAGCCTA and arrays P, Q such that:
 
        P[0] = 2 Q[0] = 4
        P[1] = 5 Q[1] = 5
        P[2] = 0 Q[2] = 6
 
The answers to these M = 3 queries are as follows:
 
· The part of the DNA between positions 2 and 4 contains nucleotides G and C (twice), whose impact factors are 3 and 2 respectively, so the answer is 2.
· The part between positions 5 and 5 contains a single nucleotide T, whose impact factor is 4, so the answer is 4.
· The part between positions 0 and 6 (the whole string) contains all nucleotides, in particular nucleotide A whose impact factor is 1, so the answer is 1.
 
Write a function:
 
        class Solution { public int[] solution(String S, int[] P, int[] Q); }
 
that, given a non-empty string S consisting of N characters and two non-empty arrays P and Q consisting of M integers, returns an array consisting of M integers specifying the consecutive answers to all queries.
 
Result array should be returned as an array of integers.
 
For example, given the string S = CAGCCTA and arrays P, Q such that:
 
        P[0] = 2 Q[0] = 4
        P[1] = 5 Q[1] = 5
        P[2] = 0 Q[2] = 6
 
the function should return the values [2, 4, 1], as explained above.
 
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 and 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.
 
Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(String S, int[] P, int[] Q)에 입력되는 S의 길이(N)는 1 ~ 100,000까지이고
P와 Q에 저장된 요소의 범위는 0 ~ N-1까지이다.
S는 A, C, G, T의 대문자로 구성된 문자열이다.

S는 DNA의 염기서열을 표현한 문자열이며, DNA는 A, C, G, T로 구성된 염기서열로 이루어진다.
염기서열은 각각 번호가 매칭되며
A = 1, C = 2, G = 3, T= 4를 의미한다.

만약 S = CAGCCTA이고 P = [2,5,0], Q = [4, 5, 6]일 때
S에서 P ~ Q 사이의 문자열을 찾는다.
예를 들어 
        P[0] = 2    Q[0] = 4    →    GCC
        P[1] = 5    Q[1] = 5    →    T
        P[2] = 0    Q[2] = 6    →    CAGCCT
이 되며, (2, 4)일 때 가장 작은 값, (5, 5)일 때 가장 작은 값, (0, 6)일 때 가장 작은 값을 찾아
정수형 배열로 만들어 반환한다.
즉 [2, 4, 1]을 반환한다.

 

풀이 - 1

class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        int[] result = new int[P.length];
        for(int i = 0; i<P.length; i++) {
            String subS = S.substring(P[i], Q[i]+1);
            if(subS.contains("A")) result[i] = 1;
            else if(subS.contains("C")) result[i] = 2;
            else if(subS.contains("G")) result[i] = 3;
            else result[i] = 4;
        }
        return result;
    }
}

 

'풀이 - 1'에 대한 회고

 

이거는 P와 Q의 값을 꺼내야 하기 때문에 무조건 반복문을 돌 수 밖에 없다.

반복문을 수행하며 S에서 값을 비교해줬더니 점수가 낮게 나왔다.

 

 

알고리즘은 정확하지만 퍼포먼스가 또 0점.

반복문 안에서 비교를 해서 그런가?

 

 

시간복잡도 또한 O(n*m)이 나왔다.

굉장히 느리다.

 

먼저 반복문으로 값을 꺼낸 후 비교는 별도로 구현해봐야겠다.

 

다른 사람의 풀이

class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        int N = S.length();
        int M = P.length;
        int[] result = new int[M];
        int[][] path = new int[4][N];
        switch (S.charAt(0)) {
            case 'A':
                path[0][0] = 1;
                break;
            case 'C':
                path[1][0] = 1;
                break;
            case 'G':
                path[2][0] = 1;
                break;
            case 'T':
                path[3][0] = 1;
                break;
        }
        
        for (int i = 1; i < N; i++) {
            char c = S.charAt(i);

            switch (c) {
                case 'A':
                    path[0][i] = path[0][i - 1] + 1;
                    path[1][i] = path[1][i - 1];
                    path[2][i] = path[2][i - 1];
                    path[3][i] = path[3][i - 1];
                    break;
                case 'C':
                    path[0][i] = path[0][i - 1];
                    path[1][i] = path[1][i - 1] + 1;
                    path[2][i] = path[2][i - 1];
                    path[3][i] = path[3][i - 1];
                    break;
                case 'G':
                    path[0][i] = path[0][i - 1];
                    path[1][i] = path[1][i - 1];
                    path[2][i] = path[2][i - 1] + 1;
                    path[3][i] = path[3][i - 1];
                    break;
                case 'T':
                    path[0][i] = path[0][i - 1];
                    path[1][i] = path[1][i - 1];
                    path[2][i] = path[2][i - 1];
                    path[3][i] = path[3][i - 1] + 1;
                    break;
            }
        }
    
        for (int i = 0; i < M; i++) {
            for (int p = 0; p < 4; p++) {
                int sub = 0;
                if (P[i] > 0) {
                    sub = path[p][P[i] - 1];
                }
    
                if (path[p][Q[i]] - sub > 0) {
                    result[i] = p + 1;
                    break;
                }
            }
        }
        return result;
    }
}

 

'다른 사람의 풀이'를 통한 회고

 

와! 이거 어려운 문제다.

소스코드도 엄청 복잡하고 조금 더 분석해봐야겠다.

아직 이해가 잘 안간다.

 

 

일단 정확성과 퍼포먼스가 100%이다.

시간 복잡도도 O(n+m)으로 '풀이 - 1'보다 훨씬 좋다.

 

 

다른 사람의 코드를 보며 힌트를 얻어 다시 풀어보려고 했는데

이 문제를 어려워하는 사람들이 많았다.

그리고 정답이라고 하는 소스코드들이 다 복잡하다.

조금 더 분석해보고 다시 풀어봐야겠다.