[python] Codility Lesson 5-2. GenomicRangeQuery

 

1. 처음 보고 prefix-sum이 아닌 나만의 풀이로 도전했다가 performance점수에서 0을 받아 62점을 받았다.

def solution(S, P, Q):
    # write your code in Python 3.6
    # A C G T 1 2 3 4
    answer_list = list()
    for j in range(len(P)):
        min_val = min(set(S[P[j]:Q[j]+1]))
        answer_list.append(min_val)
    return change_To_int(answer_list)

def change_To_int(answer_list: list)->list:
    answer = list()
    for i in range(len(answer_list)):
        if answer_list[i] == "A":
            answer.append(1)
        elif answer_list[i] == "C":
            answer.append(2)
        elif answer_list[i] == "G":
            answer.append(3)
        elif answer_list[i] == "T":
            answer.append(4)    
    return answer

 

 

2. 역시 pre-fix-sum의 개념을 사용하여야 performance 점수를 받을 수 있었다.

 

(출처 : https://davi06000.tistory.com/57)

 

pre-fix-sum 활용의 간단한 예와, 문제 적용을 잘 나타내 주셨다.

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