[Silver IV] DNA - 1969

문제

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가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

예제 입력 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

 

---

# 풀이 방법

1. “Hamming Distance가 최소”라는 의미 파악하기

from 문제) 만약에 “AGCAT"와 ”GGAAT"는 첫 번째 글자와 세 번째 글자가 다르므로 Hamming Distance는 2이다.

서로 다른 두 DNA가 비슷한 구성을 이룰수록 Hamming Distance값은 작아진다는 것을 이해

2.. “Hamming Distance가 최소”가 되기 위해 DNA s의 꼴 예측하기

입력 받은 N개의 DNA와 비슷한 구성을 이루어야 하므로

열마다 공통적으로 많이 나온 애(A,T,G,C)로 구성되면 되지 않을까?

3.  알고리즘 떠올리기

step1) N개의 DNA들은 모두 입력 받고
step2) 열마다 각각의 뉴클레오티드가 몇번 나왔는지 카운트 한다
step3) 그 중 가장 많이 나온 뉴클레오티드를 고른다.
step3) 그리고 이들로 구성된 최종 DNA s를 생성한다.
step4) Hamming Distance 계산한다. (최종 DNAs 구성으로 채택되지 않는 경우에 대한 횟수)

 

 

---

# 코드

n, m = map(int, input().split())
dna_list = [input().strip() for _ in range(n)]
result = ''
count = 0

for col in range(m):
  cnt = {'A': 0, 'C': 0, 'G': 0, 'T': 0}
  for row in range(n):
    cnt[dna_list[row][col]] += 1
  sorted_cnt = sorted(cnt.items(), key = lambda x: (-x[1],x[0]))
  result += sorted_cnt[0][0]
  count += n - sorted_cnt[0][1]

print(result)
print(count)