[Python] Codility - GenomicRangeQuery [문자열 탐색 최적화]

문제

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

GenomicRangeQuery coding task - Learn to Code - Codility

 

해설

네이버 채용 프로세스를 진행하다 Codility라는 새로운 코딩 테스트 플랫폼을 접하게 되었다. 기존 백준과 프로그래머스, leetcode와 문제 유형이 크게 다르진 않은 것 같다. 다만 코드에 점수를 매기는 방식과 시간복잡도에 대한 평가를 보여주는 것이 달랐던 점인 것 같다. 네이버 코딩테스트를 진행하기 전 시험삼아 풀어본 문제였는데 Codility 문제는 조금 더 직관적으로 코드를 풀어내는 것이 좋을 것 같다.

 

이 문제는 문자열 슬라이싱과 탐색 최적화에 대한 문제였다.

 

1차 시도(실패)

이 풀이는 정답은 맞았지만 loop 중첩으로 시간복잡도 관련 점수에 감점이 있었다. 해당 풀이의 시간복잡도는 O(N * M)이었다.

 

Fig 1. 1차 시도 결과

def solution(S, P, Q):
    result = []

    for i, v in enumerate(P):
        min_num = 5

        gen = set(S[v: Q[i] + 1])
        for g in gen:
            if g == "A":
                impact_factor = 1
            elif g == "C":
                impact_factor = 2
            elif g == "G":
                impact_factor = 3
            else:
                impact_factor = 4

            if impact_factor < min_num:
                min_num = impact_factor

        result.append(min_num)
    return result

 

2차 시도(성공)

해당 풀이의 시간복잡도는 O(N + M)이었다.

 

Fig 2. 2차 시도 결과

def solution(S, P, Q):
    result = []

    for i, v in enumerate(P):
        min_num = 5

        if "A" in S[v: Q[i] + 1]:
            impact_factor = 1
        elif "C" in S[v: Q[i] + 1]:
            impact_factor = 2
        elif "G" in S[v: Q[i] + 1]:
            impact_factor = 3
        else:
            impact_factor = 4

        if impact_factor < min_num:
            min_num = impact_factor

        result.append(min_num)
    return result