[문자열/Brute Force] 백준 1969 DNA - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1969번: DNA

 

 

 

2. 문제 풀이

 여러 DNA들간의 헤밍거리가 최소인 DNA를 만들고, 그 헤밍거리의 합을 출력하는 문제입니다.

 

2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

[Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

 DNA 염기서열은 [A, C, G, T] 중 하나로 구성되므로, 경우의 수가 4가지입니다. 브루트포스 방법으로 일일이 비교해본 뒤, 가장 헤밍거리가 작은 DNA조합을 찾을 수 있습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

#입력
N, M = map(int, input().split())
dna = []
for _ in range(N):
    dna.append(input().rstrip())

res = ''
hammingDistSum = 0

#헤밍거리 계산
for i in range(M):
    hammingDist = {'A': 0, 'C': 0, 'G': 0, 'T': 0}
    for j in range(N):
        hammingDist[dna[j][i]] += 1
    res += max(hammingDist, key=hammingDist.get)
    hammingDistSum += (N - max(hammingDist.values()))
print(res)
print(hammingDistSum)

 저는 각 DNA별 i자리의 뉴클레오티드를 조사하고, A/C/G/T 중 가장 많은 걸 배치했습니다. DNA가 여러 개 있을 경우, 사전순으로 가장 앞서는 걸 출력해야하므로, 딕셔너리 순서는 A C G T로 해야 합니다.