[ Codility 코딜리티 ] Lesson 5 GenomicRangeQuery Python 파이썬 풀이

 

// 문제 요약

 

DNA는 A,C,G,T라는 문자들로 구성된

S라는 긴 string으로 나타내 진다.

 

A,C,G,T는 각각 1,2,3,4 의

impact factor를 가진다.

 

S의 길이가 양의 정수 N이고

M개의 Query인 P,Q가 요청될때

S[P[K]] 이상 S[Q[K]] 이하의

가장 작은 impact factor는 얼마인가?

 

쿼리의 길이가 M 이므로

길이가 M인 배열로 반환하라.

 

 

// 문제 풀이

 

아주 전형적인 Prefix sum algorithm 문제다.

Prefix sum 알고리즘은 알면 풀고

모르면 못푸는 전형적인 문제라고 생각한다.

 

그러니까 아주 긴 데이터로 부터

아주 긴 쿼리가 요청될때는

O(M * N)이 되므로 사실상

O(N**2) 보다 더 커질 수도 있다.

따라서 이걸 O(N+M)까지 낮추는 방법이 바로

prefix sum 알고리즘 이다.

 

쿼리는 데이터베이스에 자료를 요청하는

일련의 신호를 말한다.

 

prefix sum을 간략하게 설명하자면

데이터베이스를 전처리하여

쿼리의 요청에 최적화된 상태로 먼저 만들고

쿼리의 요청을 읽어들이는 방식이다.

 

즉

[ a1, a2, a3, a4, a5, ... ]

와 같은 데이터가 있으면

[a1, a1+a2, a1+a2+a3, a1+a2+a3+a4, ...]

와 같이 전처리를 해둔다. ( O(N) )

 

그러면 쿼리의 요청에 따라

(a1+a2+a3+a4+a5)

(a1+a2+a3+a4+a5+a6)

이라는 두 수를 불러오고 빼면

a6의 값이 무엇인지 바로 알 수 있는( O(1) )

혹은 

(a1+a2+a3)

(a1+a2+a3+a4+a5+a6)

을 서로 빼면 a3으로 부터 a6까지

얼마가 증가했는지 바로 알 수 있는( O(1) )

상태로 바뀌기 때문에

이것을 M번 반복하면 ( O(M) )

 

서로 독립적인 2개의 for문으로 만들어서

O(N+M) 으로 알고리즘을 짜는 것이 가능하다.

 

 

일단 코드를 보자.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(S, P, Q):
    # write your code in Python 3.6
    # you can write to stdout for debugging purposes, e.g.
    # print("this is a debug message")
    A, C, G, T = 0, 0, 0, 0

    cummulated = [[0, 0, 0, 0]]
    for char in S:
        if char == "A":
            A += 1
        elif char == "C":
            C += 1
        elif char == "G":
            G += 1
        elif char == "T":
            T += 1
        cummulated.append([A, C, G, T])

    i_f_table = {"A": 1, "C": 2, "G": 3, "T": 4}
    answer = []
    for p, q in zip(P, Q):
        left, right = cummulated[p], cummulated[q + 1]
        if left[0] != right[0]:
            answer.append(1)
        elif left[1] != right[1]:
            answer.append(2)
        elif left[2] != right[2]:
            answer.append(3)
        elif left[3] != right[3]:
            answer.append(4)
        else:
            answer.append(i_f_table[S[p]])
    return answer

솔직히 개인적으로

이 풀이가 우아하다고 생각하지 않는다..

어떻게든 정리하여

깔끔하고 범용적인 형태의 코드로

만들어보려고 했으나

파이썬의 copy 때문에

cumulation이 잘 되지 않아

그냥 이렇게 적었다.

 

위의 경우 AGCT 네가지 cumulater를 만든다.

만약에 각각의 원소가 발현되면

1을 더해주고 아니면 0을 더한다.

 

이렇게 되면 쿼리로 뽑아낸 양끝값이

같은지 같지 않은지만 보아도

중간에 이 값이 발현을 했는지 안했는지

바로 알 수 있다.