Codility: GenomicRangeQuery (Python)

주제

Lesson 5: Prefix Sums

 

난이도

Medium

 

문제

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:
def solution(S, P, 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, 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.

 

문제를 이해하는데 좀 오래걸렸으나 결국은 주어진 P와 Q의 값을 이용해 염기서열 S의 index 범위를 한정 짓고, 그 범위 내에 가장 작은 impact factor를 구하는 것이다. impact factor는 A :1, C :2, G :3, T :4 이다. 

염기서열 S는 배열로 들어오며, 길이는 N이고, M은 쿼리의 수로, P와 Q의 개수라고 볼 수 있다. 

P와 Q의 원소는 0~N-1로 염기서열의 index를 뜻한다.

S는 A, C, G, T 로만 이뤄져있다. 

 

문제 풀이과정은 efficient해야한다.

 

* 문제 이해는 bold체로 된 예시 부분을 읽으면 도움이 될 것 같다. 

 

풀이

이번 문제도 역시나 바로 효율적인 답안을 찾을 수 없었다. 정확히는 찾지 못해서 결국 구글신의 도움을 받았다...

그래도 이해했으면 된거지 모... (불타는 행복회로)

 

(1) O(M*N)

일단 염기 서열에 따른 값(impact factor)를 짝지어 주기 위해서 딕셔너리로 정리해주었다. 그리고 매 쿼리마다의 최소값을 리스트로 저장해 반환해야하므로 min_list를 만들어주었다.

 

  - 염기서열을 slicing할 index값인 P, Q는 총 M개의 원소를 갖기 때문에 0~M-1까지 반복하면서 P[i], Q[i]의 index값을 불러왔다. 

  - P[i]와 Q[i]값 중 큰 값을 뒤로 해서 염기서열 S를 slicing 해준다. (단, slice할 때, 맨 뒤의 index는 포함이 되지 않으므로 +1 해서 slice 해준다.)

  - 공교롭게도 알파벳 순서(A < C < G < T)와 impact factor의 크기 순서 (1 < 2 < 3 < 4)가 같으므로 위에서 slice한 리스트의 최소값을 반환받은 후 딕셔너리를 이용해 impact factor 값을 구한다. 해당 값을 min_list에 append해준다.

  - 위의 반복문을 다 돈 후에 min_list 를 반환한다. 

 

위처럼 접근하면 slicing한 배열에서 min함수를 쓸 때, O(N)이므로 결국 O(M*N)이 된다. 그래서 codility에 채점하면 performance 점수가 0이 나온다...

 

 

(2) O(M+N)

솔직하게 codility의 prefix sum 단원을 풀면서 prefix sum을 이용해야한다고 깨달은 것은 이 문제가 처음이었다!

 그 동안 lesson에 상관없이 효율적으로 풀려고 했었는데, 이번 문제를 풀면서 괜히 카테고리를 나눠둔게 아니구나 싶긴 했다. (물론 이 생각은 맨 마지막인 MinAvgTwoSlice 문제를 품과 동시에 사라졌다.) 여튼 각설하고, 풀이는 아래와 같다.

 

- 염기서열을 보면서 index에 맞춰서 어떤 문자가 나타났는지를 표시할 것이다. 예를 들어 맨 처음에 A가 나타났다면, A를 1로 표현하고, 나머지 C, G, T는 나오지 않았으므로 0으로 표시한다. 만약 그다음에도 A가 나타난다면 1을 표시하되, 전에도 A가 있었으므로 2를 저장하고, 나머지는 여전히 0으로 저장한다. 이런 식으로 나타나면 1로 표시하고 그 전에 있던 값들에다가 꾸준히 더해간다. 예를 들어서 AACGT라는 염기서열이 있다면 아래와 같이 풀릴 것이다.

 

index	염기서열	A 발생 리스트 (a_list)	C 발생 리스트 (c_list)	G 발생 리스트 (g_list)	(T 발생 리스트) (t_list)
0	A	1	0	0	0
1	A	12	00	00	00
2	C	122	001	000	000
3	G	1222	0011	0001	0000
4	T	12222	00111	00011	00001

 

위의 표처럼 정리하게 되면 결국 특정 index로 나눠서 볼 경우 해당 index의 prefix sum을 확인해서 차이가 0이라면 그 구간동안 해당 문자가 발생하지 않은 것으로 해석이 가능하다. 

즉, 위의 표를 기준으로 만약 S[2:4]에서 A가 발생했는지 여부를 판단한다면 a_list[4] - a_list[2] = 2-2 = 0이므로, 그 사이에 A가 한번도 나타나지 않았음을 알 수 있다.

 

따라서 O(M*N)에서 푼 것 처럼 P,Q를 M만큼 반복하면서 P[i]와 Q[i]의 index를 이용해 각각 A, C, G가 있는지 파악한다. 만약 세 경우 다 없다고 판단이 된다면 T가 된다. (최소를 찾으라고 했으므로, A -> C -> G 순으로 찾고, 만약 없다면 T라고 결정한다. 굳이 T에 대한 데이터도 저장할 필요가 없다. - 따라서 위의 표에도 회색으로 표시했다.-)

 

결국은 유무를 binary(0 or 1)로 표현 후 prefix sum으로 표현해서 문제 해결을 용이하게 만드는 것이다.    

 

 

※ 참고한 자료는 https://stackoverflow.com/questions/19552754/java-codility-training-genomic-range-query 이다. ※

 

코드

(1) O(M*N)

impact_factor_dict = {'A':1, 'C':2, 'G':3, 'T':4}

def solution(S, P, Q):
    M = len(P)
    min_list = []
    for i in range(M):
        point_p = P[i]
        point_q = Q[i]

        if point_p >= point_q:
            find_area = S[point_q:point_p+1]
        else:
            find_area = S[point_p:point_q+1]

        min_val = impact_factor_dict[min(find_area)]
        min_list.append(min_val)

    return max_list

 

(2) O(M+N)

def solution(S, P, Q):
    # 맨 첫 원소는 0으로 셋팅함.
    binary_DNA = {'A':[0], 'C':[0], 'G':[0]}
    # S를 하나씩 보면서 해당 문자는 1, 아닌 문자는 0으로 표현한다.
    # 그 후 위치에 따라 계속 prefix sum을 진행한다.
    # 예를 들어서 AACGT라면 -> A : 12 222, C : 00 111, G: 00011 ... 이런식으로 진행이 될것이다.
    # 즉, 특정 idx로 나눠서 볼 경우 해당 idx의 prefix sum을 확인해서 차이가 0이면 그 구간동안 해당 문자가 발생하지 않은 것으로 해석가능.
    for idx, dna in enumerate(S):
        a = 0
        c = 0
        g = 0
        if dna == 'A':
            a = 1
        elif dna == 'C':
            c = 1
        elif dna == 'G':
            g = 1

        binary_DNA['A'].append(binary_DNA['A'][idx] + a)
        binary_DNA['C'].append(binary_DNA['C'][idx] + c)
        binary_DNA['G'].append(binary_DNA['G'][idx] + g)

    M = len(P)
    min_list = []
    for i in range(M):
        point_p = P[i]
        point_q = Q[i]

        # binary_DNA의 리스트들이 다 0으로 시작했기 때문에 마지막 index는 +1로 늘려줘야 순서가 맞다!
        if point_p >= point_q:
            start = point_q
            end = point_p+1
        else:
            start = point_p
            end = point_q+1

        # check existence
        if binary_DNA['A'][end] - binary_DNA['A'][start] > 0:
            min_list.append(1)
        elif binary_DNA['C'][end] - binary_DNA['C'][start] > 0:
            min_list.append(2)
        elif binary_DNA['G'][end] - binary_DNA['G'][start] > 0:
            min_list.append(3)
        else:
            min_list.append(4)

    return min_list

 

 

시간복잡도

(1) O(M*N)

for 반복문 : O(M)

반복문 내부의 min 함수 : O(N)

따라서 O(M*N)이 된다.

 

(2) O(M+N)

prefix sum을 구하는 과정의 반복문 : O(N)

P, Q를 반복하면서 확인하는 반복문 : O(M)

따라서 O(N+M)이 된다.

 

결과

codility 결과

 

codility 시간 복잡도