[Codility] GenomicRangeQuery

풀이

def accumulator(index, target_DNA, DNA_mapper):
    for DNA in DNA_mapper:
        if target_DNA == DNA:
            DNA_mapper[target_DNA][index + 1] = DNA_mapper[target_DNA][index] + 1
        else:
            DNA_mapper[DNA][index + 1] = DNA_mapper[DNA][index]

def get_minumum_impact_factor(start_index, end_index, DNA_mapper):
    for DNA in DNA_mapper:
        if DNA_mapper[DNA][end_index + 1] - DNA_mapper[DNA][start_index] > 0:
            return DNA
    else:
        return 'T'

def solution(S, P, Q):
    answer = []
    impact_factor = {
        'A': 1,
        'C': 2,
        'G': 3,
        'T': 4
    }
    # A - C - G - T 순으로 존재하는지 검사해야함
    # min factor 하나만 저장하는 것이 아니라 factor별로 구간 누적 값을 갖고 있어야
    # 해당 구간에 해당 factor가 있는지 없는지를 바로 알 수 있다. 
    A, C, G = [0] * (len(S) + 1), [0] * (len(S) + 1), [0] * (len(S) + 1)
    DNA_mapper = {
        'A': A,
        'C': C,
        'G': G
    }
    for i, DNA in enumerate(S):
        accumulator(i, DNA, DNA_mapper)


    for i, j in zip(P, Q):
        minumum = get_minumum_impact_factor(i, j, DNA_mapper)
        answer.append(impact_factor[minumum])

    return answer

포인트

prefix sums 개념을 응용해서 푸는 문제. array slice에 대해 매번 최소값을 찾고자 한다면 O(N * M) 만큼 시간이 걸린다. prefix sums가 합계를 누적해서 어떤 구간의 합계를 빨리 구하는 방법이듯이, 이 문제도 어떤 구간의 최소값을 빨리 구해야 한다. 맨 처음에는 하나의 배열에 최소값을 누적하려나 생각했는데, 그건 의미가 없다. 인덱스 0에 A가 나타나면 그 뒤에 오는 어떤 인덱스까지의 범위에도 최소값은 A인데, 정작 우리가 구하려는 구간에 A가 있음을 확신할 수는 없기 때문이다.

그러므로 검사하는 해당 구간에 A가 존재하는지, 그 다음으로는 C가 존재하는지, 그 다음으로는 G가 존재하는지 한 번에 알 수 있는 방법이 필요하다. DNA별로 각각 배열을 만들어서 누적 카운트를 저장하고, index로 접근해서 카운트 변동이 그 구간에 없었으면 검사하는 DNA가 그 구간에 나타나지 않았음을 알 수 있다.

Ref

코딜리티