[Codility5/Lesson]GenomicRangeQuery(python)

| 1트

def solution(S, P, Q):
    hash_alpha = {'A' : 1, 'C' : 2, 'G' : 3, 'T': 4 }
    answer_list = list()

    for i, (p , q) in enumerate(zip(P, Q)):
        min_num = sorted(S[p:q+1])[0]
        answer_list.append(hash_alpha[min_num])
    
    return answer_list

결과는 여기서

음 느려ㅠ ㅠ
앞에가 되는게 더 신기하다
그리고 참고로 sort 후 [0] 보다는 min이 더 빠르다고 한다
하지만 이 문제는 min으로도 되지 않는다
사실상 min이 O(n)이니까 거의 for문 두번 돌린것과 같다는 것

sort 후 [0] vs min() 시간복잡도

| 2트

def solution(S, P, Q):
    hash_alpha = {'A' : 1, 'C' : 2, 'G' : 3, 'T': 4 }
    answer_list = list()

    for i, (p , q) in enumerate(zip(P, Q)):
        if 'A' in S[p:q+1]:
            answer_list.append(hash_alpha['A']) 
        elif 'C' in S[p:q+1]:
            answer_list.append(hash_alpha['C'])
        elif 'G' in S[p:q+1]:
            answer_list.append(hash_alpha['G'])
        else:
            answer_list.append(hash_alpha['T'])
    
    return answer_list

• in 은 시간 복잡도가 O(1) ~ O(n)이기 때문에 가능한 듯 하다
• 흠..