[🥈5 / 백준 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 s₁, s₂, ..., s_n가 주어져 있을 때 Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 s₁의 Hamming Distance + s와 s₂의 Hamming Distance + s와 s₃의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.

입력

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

출력

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

 

예제 입력 1 5 8 TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT	예제 출력 1 TAAGATAC 7
예제 입력 2 4 10 ACGTACGTAC CCGTACGTAG GCGTACGTAT TCGTACGTAA	예제 출력 2 ACGTACGTAA 6
예제 입력 3 6 10 ATGTTACCAT AAGTTACGAT AACAAAGCAA AAGTTACCTT AAGTTACCAA TACTTACCAA	예제 출력 3 AAGTTACCAA 12

 

풀이

 

n개의 염기서열과 모두 비교했을 때, Hamming Distance가 가장 적은 염기서열을 만들어서 출력해야 한다.

주의할 점은 n개의 염기서열 중 하나를 골라 출력하는 것이 아니라 직접 생성해야 한다는 것이다.

 

이 작업을 위해 각 염기서열을 세로로 비교할 것이다.

세로로 비교했을 때, 가장 많이 나온 것을 하나씩 뽑아 출력할 염기서열을 생성한다.

 

사전순으로 앞서는 것을 출력해야 하므로, ACGT 순서로 비교한다.

 

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
dna = [input().rstrip() for _ in range(n)]
acgt = {"A":0, "C":1, "G":2, "T":3}
acgt_reverse = {0:"A", 1:"C", 2:"G", 3:"T"}
ans = ""
ans_sum = 0

for i in range(m):
    cnt = [0,0,0,0] // ACGT
    for j in range(n):
        cnt[acgt[dna[j][i]]] += 1
    
    min_idx = -1
    max_cnt = 0
    for idx in range(4):
        if cnt[idx] == 0:
            continue
        if cnt[idx] > max_cnt:
            max_cnt = cnt[idx]
            min_idx = idx
            
    ans += acgt_reverse[min_idx]
    ans_sum += n-max_cnt
print(ans, ans_sum, sep="\n")