(코딜리티) Lesson 5 : GenomicRangeQuery- Python

이 문제는 prefix sum 알고리즘에 대한 이해도가 있어야 풀 수 있다고 생각됩니다. 

처음에 풀지 못하고, prefix sum에 대한 알고리즘을 알고 난 뒤 응용하여 문제를 풀었습니다. 

제 머리는 prefix sum이라는 알고리즘을 모르고 문제를 푸는 건 절대 머리속에서 나올 수가 없다고 생각이 드네요..ㅠㅠ

 

문제 : app.codility.com/programmers/lessons/5-prefix_sums/

5. Prefix Sums lesson - Learn to Code - Codility

문제설명

A, C, G, T라는 뉴클레오타이드가 있습니다. 각각의 영향도는 1, 2, 3, 4로 나타내며 이 영향을 최소화 하는 DNA의 순서를 알고 싶습니다.

 

S는 S[0]S[1]...S[N-1]로 구성되며, M개 배열인 쿼리가 주어집니다.

 

예를 들어, S=CAGCCTA와 배열인 P = [2, 5, 0], Q = [4, 5, 6]가 주어집니다.

P[0], Q[0] = 2, 4일 때, 2와 4사이의 뉴클레오타이드는 G, C, C이며, 이중 최소값은 C인 2입니다.

P[1], Q[1] = 5, 5일 때, 5와 5사이의 뉴클레오타이드는 T 하나 뿐이며, 따라서 최소값은 T인 4입니다.

P[2], Q[2] = 5, 5일 때, 0와 6사이의 뉴클레오타이드는 C부터 A까지이며, 이중 최소값은 A인 1입니다.

 

따라서, [2, 4, 1]을 return해야합니다.

제한 사항

• N은 1~100,000 사이 입니다.
• M은 1~50,000 사이 입니다.
• P와 Q 각 배열의 값은 0~N-1입니다.
• P[K] <= Q[K]이며, 0<=K<M 입니다. (사실상 K는 M-1아닌가..?)
• S는 대문자 A, C, G, T로 구성되어 있습니다.

코드

def solution(S, P, Q):
    
    impact_score = ['A', 'C', 'G', 'T']		#ACGT의 impact점수를 알 수 있는 list
    prefix = [[0, 0, 0, 0]] 	#prefix sum을 활용하기 위한 list
    result = []  #최종 결과를 return하기 위한 list
    
    # prefix sum을 위한 for문
    for s in S:    
        prefix_list = prefix[-1].copy()		#누적 카운터를 위해 마지막 list를 가져오고, copy를 이용해 prefix안의 list에 영향을 주지 않도록 함
        prefix_list[impact_score.index(s)] += 1
        prefix.append(prefix_list)
	
    # 결과값 도출을 위한 for문
    for i, j in zip(P, Q):
    	
        #만약 i와 j가 같으면 (0, 0, 0, 0)이 나오므로, 알파벳의 점수를 바로 환산
        if i==j:
            result.append(impact_score.index(S[i])+1)
            continue
		
        # ex) python에서 [0, 3, 1, 0] - [0, 1, 1, 0]은 바로 구할 수 없어서 for문을 활용하여 구함
        temp_list = [a-b for a,b in zip(prefix[j+1],prefix[i])]
        
        # 결과 list에서 순서대로 확인 후 1 이상으로 나오면 제일 작은 값으로 index +1로 result에 추가
        for k, p in enumerate(temp_list):
            if p > 0:
                result.append(k+1)
                break
            
    return result

해설

이 부분은 prefix sum으로 구간 합을 구하는 prefix = [[0, 0, 0, 0]] 이 부분을 이해하실 수 있다면, 다른 부분은 주석만 보고 이해하실 수 있다고 생각합니다.