[codility] GenomicRangeQuery

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

GenomicRangeQuery coding task - Learn to Code - Codility

min에서 모두 탐색했더니 시간초과 뜬다

62프로

O(n*m)을 곱셈이 아닌 것으로 풀려면 for문 대신 저장할 수 있는 변수를 추가해야하는데

def solution(S, P, Q):
    # write your code in Python 3.6
    m = len(P)
    d={'A':1,'C':2,'G':3,'T':4}
    a=[ d[min(S[P[i]:Q[i]+1])] for i in range(m)]
    return a

 

부분집합을 만드는 문제들은

미리 sum(1), sum(2), ... sum(N)을 만들어두고 => 여기서 O(N)으로 미리 만들고

a(2~4)를 물으면 sum(4) - sum(1)을 해줘서 O(1)로 계산하도록 하나봄

 

오오 그리고 신기한 것 또 알았따

a.append(p)와 a.append(p[:])는 다름!!

p는 포인터 값이 복사되고 p[:]는 p 배열 값이 복사됨 

 

Q[i]+1인 이유는 a에 이미 [0]*4가 들어가있어서 index가 하나 증가한 상태임

j는 a,c,g,t 순서로 0,1,2,3이라서 1씩 더해주면 1,2,3,4로 나옴

def solution(S, P, Q):
    # write your code in Python 3.6
    a = [[0,0,0,0]]
    d = {'A':1,'C':2,'G':3,'T':4}
    p = [0]*4
    for i in S:
        p[d[i]-1] += 1
        a.append(p[:])

    ret = []
    m = len(P)
    for i in range(m):
        for j in range(4):
            tmp = a[Q[i]+1][j] - a[P[i]][j]
            if tmp !=0:
                ret.append(j+1)
                break
    return ret