문제 링크

https://www.hackerrank.com/challenges/determining-dna-health/problem

주의사항

주어진 DNA 종류의 개수와 DNA strands의 길이의 최댓값이 10의 5승까지 가능하므로 시간복잡도 O(NlogN) 안에 최대한 해결해야 함

• DNA strands의 substring을 돌며 DNA 종류 비교하는 방식으로 계산하면 시간초과 발생할 것
• 풀이과정
  - defaultdict를 활용하여 각 DNA의 health 정보(누적합)를 저장
  - bisect를 활용해 index와 first, last 비교하여 그 구간 안에 있는 health 정보만 불러오기

문제 풀이

from math import inf
from collections import defaultdict
from bisect import bisect_left, bisect_right

def getHealth(seq, first, last, longest):
    h, ls = 0, len(seq)
    
    for l in range(ls):
        for k in range(1, longest+1):
            if l+k > ls:
                break
            sub = seq[l:l+k]
            if sub not in sub_d: 
            # if AA not in subs, AAA also not in subs
                break
            if sub not in gDict: 
            # if AA not in subs, AAA can be in gDict
                continue
            idxs, hs = gDict[sub]
            
            right = hs[bisect_right(idxs, last)] # O(logN)
            left = hs[bisect_left(idxs, first)]  # O(logN)
            
            h += (right - left)
    return h

if __name__ == '__main__':
    n = int(input().strip())
    genes = input().rstrip().split()
    health = list(map(int, input().rstrip().split()))
    gDict = defaultdict(lambda : [[], [0]]) # gene_idx, health
    sub_d = set() # substring of d
    
    for i, gene in enumerate(genes):
        gDict[gene][0].append(i) 
        # append gene index
        for j in range(1, min(len(gene), 50)+1):
            sub_d.add(gene[:j]) 
            # add substrings to subs
            
    for v in gDict.values():
        for i, idx in enumerate(v[0]):
            v[1].append(v[1][i]+health[idx]) 
            # cumulative sum of health (first index = 0)
    
    longest = max(list(map(len, genes))) # longest length of genes
    hMin, hMax = inf, 0

    s = int(input().strip())

    for s_itr in range(s):
        first_multiple_input = input().rstrip().split()

        first = int(first_multiple_input[0])

        last = int(first_multiple_input[1])

        d = first_multiple_input[2]
        
        h = getHealth(d, first, last, longest)
        hMin, hMax = min(hMin,h), max(hMax,h)

    print(hMin, hMax)

궁금한 점

• 코드 37번째 줄에서 for j in range(1, min(len(gene), 50)+1): 로 substring의 길이를 최대 50까지 제한하는 줄이 있다.
• 이 50이라는 기준을 500 -> 100 -> 50까지 줄여도 문제가 없어서 다른 사람들의 풀이 중 500이었던 숫자를 50까지 줄여서 사용했다.
• 여기서 보다 정확한 substring 길이의 제한을 설정하기 위해선 문제에서 어떤 조건을 보아야 했던 건지 아직도 의문이다.
• 혹시 정확히 알고 계신 분이 있다면 댓글로 알려주시면 감사하겠습니다..