[Codility] Lesson5.Genomicrangequery (Python)

1. 문제

app.codility.com/c/run/training7N2BZJ-DMG/

Codility

2. 풀이

주어진 구간의 string에서 충격계수가 작은 값을 반환하는 문제

시간복잡도에서 점수를 못 받아서 다른 사람들이 푼 코드를 보고 해결했다.

prefix sum(구간합) 알고리즘을 사용해야 한다.

근데 if문으로 간단하게 푼 솔루션이있어 if문으로 단번에 해결했다.

 

3. 코드

# A, C, G, T
# 1, 2, 3, 4
#해당구간의 string에서 가장 작은 충격계수 반환

def solution(S, P, Q):
    res = []
    for i in range(len(P)):
        tmpStr = S[P[i]: Q[i]+1]
        if 'A' in tmpStr:
            res.append(1)
        elif 'C' in tmpStr:
            res.append(2)
        elif 'G' in tmpStr:
            res.append(3)
        else:
            res.append(4)
    return res

 

 

---

prefix sum 알고리즘 설명 : hyeri0903.tistory.com/165

Prefix Sum 구간합