[ Codility ] GenomicRangeQuery - python

개념

Lesson 5. Prefix Sums 두 번째 문제

 

문제요약

A,C,G,T 네 종류의 dna 시퀀스가 있고, 각각 1,2,3,4 의 impact factors를 갖고 있음. 네 알파벳이 섞인 문자열 S와  시작 인덱스 범위를 원소로 갖는 리스트 P, 마지막 인덱스 범위를 원소로 갖는 리스트 Q가 입력으로 주어짐. P와 Q의 동일 인덱스 값이 각각 문자열에서 확인할 인덱스의 시작범위와 끝 범위를 의미함. 처음 주어진 문자열에서 P,Q에 주어진 범위 인덱스만을 볼 때 가장 impact factor가 작은 값을 리스트에 담아 리턴하면 됨. ( 결과적으로 리스트에는 P 또는 Q의 원소 개수 만큼 값이 들어있음 )

 

첫번째 접근(효율성 고려X) 

문제에서 풀이한 방식 그대로 코드 구현

def solution(S, P, Q):

    d = {"A":1,"C":2,"G":3,"T":4} # 01 값 비교를 위한 딕셔너리 생성
    n = len(P)
    r = []
    
    for i in range(n):
    	# 02 원하는 문자열 범위 구하기 - 슬라이싱
        new_s = S[P[i]:Q[i]+1]
        
        # 03 초기값 설정
        minV = d[new_s[0]]
        
        # 04 새로 생성한 문자열을 돌면서 가장 작은 impact factor값으로 minV 값 갱신
        for dna in new_s:
            if d[dna] < minV:
                minV = d[dna]
        
        # 05 최소값을 최종 리턴할 리스트에 추가
        r.append(minV)
        
    return r

정답은 맞췄지만 시간초과

for문 안에서 for문을 한 번 더 돌아서 시간복잡도는 O(N*M)

 

두번째 접근(효율성을 고려했지만 통과는 못한 코드)

아래에 있는 세 가지 버전 모두 62%로 효율성 테스트는 통과하지 못함 (시간복잡도는 모두 O(N*M))

def solution(S, P, Q):
    d = {"A":1,"C":2,"G":3,"T":4}
    n = len(P)
    r = []
    for i in range(n):
        new_s = S[P[i]:Q[i]+1]
        minV = d[new_s[0]]
        tmp = [] # 이미 impact factor 확인한 적 있는 문자인지 확인하려는 용도
        for dna in new_s:
            if dna == "A": # 혹시 가장 작은 값이 있으면 바로 멈추기
                minV = 1
                break
            if dna not in tmp:
                tmp.append(dna) 
            if d[dna] < minV:
                minV = d[dna]
            if len(tmp) == 4: # 4개의 알파벳을 모두 판별했다면 더 검사할것 없이 멈추기
                break
        r.append(minV)
    return r

def solution(S, P, Q):
    d = {"A":1,"C":2,"G":3,"T":4}
    n = len(P)
    r = []
    for i in range(n):
    	# 세트로 중복 제거 먼저 해버리는 방법
        tmp = list(set(S[P[i]:Q[i]+1]))
        minV = d[tmp[0]]
        for dna in tmp:
            if d[dna] < minV:
                minV = d[dna]
        r.append(minV)
    return r

def solution(S, P, Q):
    d = {"A":1,"C":2,"G":3,"T":4}
    r = []
    for i in range(len(P)):
    	# 문자열에서 그냥 가장 작은(오름차순으로 앞에있는) 알파벳의 밸류값
        r.append(d[min(S[P[i]:Q[i]+1])])
    return r

여기까지는 죄다 타임아웃

 

마지막 접근(통과한 코드)

혹시 이건 되려나 하고 돌려본 코드인데 통과되어버린..? 코드 (시간복잡도는 모두 O(N+M))

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

 

 

코드 리뷰

1. 파이썬 내장 함수의 시간복잡도를 보면 min,max도 O(N)이고 값의 존재여부를 찾는 in도 O(N)인데 왜 앞의 코드들은 N*M이고 마지막 코드는 N+M인지 고민을 많이 해야 했던 코드. 나름의 결론은 앞의 코드들은 거의 확실(?)하게 for문 안에서 다시 한 번 문자열을 순회하는데 마지막 코드는 순회 도중에 값을 발견하면 바로 찾을 수 있어서 이렇게 나왔을 수 있겠다는 생각. 하지만 Big-O는 상수항이나 계수부분을 날린다는 점을 생각해보면 테스트케이스에 따라서 다른 결과가 나올수도 있지 않았을까 함.

2. 문자열의 일부를 따로 볼 때는 슬라이싱을 활용하는게 빠름