[Python/파이썬] 백준 1969번 DNA

1969번: DNA

 

문제

DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오티드의 첫글자를 따서 표현한다. 만약에 Thymine-Adenine-Adenine-Cytosine-Thymine-Guanine-Cytosine-Cytosine-Guanine-Adenine-Thymine로 이루어진 DNA가 있다고 하면, “TAACTGCCGAT”로 표현할 수 있다. 그리고 Hamming Distance란 길이가 같은 두 DNA가 있을 때, 각 위치의 뉴클오티드 문자가 다른 것의 개수이다. 만약에 “AGCAT"와 ”GGAAT"는 첫 번째 글자와 세 번째 글자가 다르므로 Hamming Distance는 2이다.

우리가 할 일은 다음과 같다. N개의 길이 M인 DNA s1, s2, ..., sn가 주어져 있을 때 Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 s1의 Hamming Distance + s와 s2의 Hamming Distance + s와 s3의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.

입력

첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

코드

n, m = map(int, input().split())
dna = []
for _ in range(n):
    dna.append(input())
    
ans_dna = ''
ans_hd = 0
for i in range(m):
    nt = {'A':0, 'C':0, 'G':0, 'T': 0}
    for j in range(n):
        nt[dna[j][i]] += 1
    res = ''
    max_v = -1
    for k, v in nt.items():
        if v > max_v:
            max_v = v
            res = k
    ans_dna += res
    ans_hd += (n-max_v)

print(ans_dna, ans_hd, sep='\n')

 

처음에 입력으로 받은 DNA들 중 다른 DNA들과 Hamming Distance가 다른 DNA를 찾는 문제인줄 알고 잘못 풀어서 한참 헤맸다....근데 다시 보니까 입력으로 받은 것들 중에 찾는게 아니어서 위와 같이 풀이하였다.

 

1. 입력으로 받은 DNA들 중 같은 위치의 글자들의 개수를 센다.
2. 개수가 가장 많은 문자를 선택해야 Hamming Distance가 최소가 될 것이다. 개수가 최대인 문자를 찾고 이 문자의 개수를 n에서 뺀 값을 Hamming Distance를 저장할 변수인 ans_hd에 더하여 준다.