[알고리즘][Python] 백준(BOJ) 1969 DNA_파이썬

 

1969 DNA    www.acmicpc.net/problem/1969

1969번: DNA

 

 

 

문제 풀기 전 공부할 것 : 브루트포스 알고리즘

 

 

 

 

 

 

 

풀이

<내용>

• Hamming Distance의 합이 가장 작은 DNA 중 사전 순으로 가장 앞서는 것을 구하는 것이므로 같은 위치에 있는 DNA를 비교하면 된다.
• 같은 위치에 있는 DNA 중 가장 많은 뉴클레오티드로 이루어진 것 중 사전 순으로 가장 앞서는 것을 res에 더해주고 그것을 제외한 뉴클레오티드를 cnt에 더해준다.

 

 

<코드>

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
dna = [input().rstrip() for _ in range(n)]

dna_to_num = {'A':0, 'C':1, 'G':2, 'T':3}
num_to_dna = {0:'A', 1:'C', 2:'G', 3:'T'}

res = ''
cnt = 0

for d in range(m):
    check = [0] * 4    
    for i in range(n):
        check[dna_to_num[dna[i][d]]] += 1
    
    max_dna = max(check)
    max_dna_idx = check.index(max_dna)
    res += num_to_dna[max_dna_idx]
    check[max_dna_idx] = 0
    cnt += sum(check)
    
                
print(res)
print(cnt)