[Python] 5.2. GenomicRangeQuery

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

5. Prefix Sums lesson - Learn to Code - Codility

 

---

1차 시도

Task Score
62%
Correctness
100%
Performance

0%

시간복잡도 O(N*M)

def solution(S, P, Q):

    impact_factor = {"A":1,"C":2,"G":3,"T":4}
    lst = []
    for K in range(len(P)):
        queries = set(S[P[K]:Q[K]+1])
        min_val = 9
        for q in queries:
            if impact_factor[q] < min_val:
                min_val = impact_factor[q]
        lst.append(min_val)

    return lst

2차 시도 - Prefix 테크닉 적용

Task Score

100%

Correctness

100%

Performance

100%

시간복잡도 O(N + M)

def solution(S, P, Q):

    dic = {"A":1, "C":2, "G":3, "T":4}
    lst = [0]*5
    prefix = []
    answer = []
    for s in S:
        lst[dic[s]] += 1 
        prefix.append(lst.copy())

    M = len(P)

    for k in range(M):
        if P[k] == 0:
            result = [prefix[Q[k]][i]-[0,0,0,0,0][i] for i in range(len(lst))]
        else:
            result = [prefix[Q[k]][i]-prefix[P[k]-1][i] for i in range(len(lst))]
        for r in range(len(result)):
            if result[r] != 0:
                answer.append(r)
                break

    return answer