문제
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 | 예제 입력 2 | 예제 입력 3 |
|---|---|---|
5 8 TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT | 4 10 ACGTACGTAC CCGTACGTAG GCGTACGTAT TCGTACGTAA | 6 10 ATGTTACCAT AAGTTACGAT AACAAAGCAA AAGTTACCTT AAGTTACCAA TACTTACCAA |
| 예제 출력 1 | 예제 출력 2 | 예제 출력3 |
TAAGATAC 7 | ACGTACGTAA 6 | AAGTTACCAA 12 |
import sys
n, m = map(int, input().split())
dna_list = []
for i in range(n):
dna_list.append(sys.stdin.readline().replace('\n', ''))
cnt_dict = dict()
hd = 0
result = ''
for i in range(m):
cnt_dict.update(zip([chr(i) for i in range(ord('A'), ord('Z')+1)], [0 for i in range(26)]))
for j in range(n):
cnt_dict[dna_list[j][i]] += 1
max = 0
alpha =''
for k in range(ord('A'), ord('Z')+1):
if max < cnt_dict[chr(k)]:
max = cnt_dict[chr(k)]
alpha = chr(k)
hd += cnt_dict[chr(k)]
result += alpha
hd -= cnt_dict[alpha]
print(result)
print(hd)브루트포스로 입력으로 주어진 DNA의 모든 인덱스를 돌며 답을 구했다. DNA의 길이만큼 반복하며 A부터Z까지의 key로 이루어져있고 모든 value가 0으로 셋팅된 딕셔너리를 만들고 DNA 리스트의 해당 인덱스에 나오는 알파벳을 key로 하여 해당 key의 value를 1씩 증가시켜주었다.
모든 DNA의 해당 인덱스 탐색이 끝나면 알파벳의 갯수만큼 value가 카운팅된 딕셔너리에서 value의 최대값을 구한 후 결과로 출력할 DNA에 해당 알파벳을 열결해준다.
hamming distance의 합은 DNA의 모든 알파벳의 수에서 각 인덱스별 value의 최대값을 빼주는 방법으로 구했다.
딕셔너리에 알파벳 순서대로 key를 추가하기 위해 chr(i) for i in range(ord('A'), ord('Z')+1)를 사용했다. ord는 괄호 안의 문자를 아스키 숫자로 바꿔주는 함수이고 그 'A'부터 'Z'까지의 아스키를 차례로 i에 넣어주며 chr()함수를 통해 i의 값을 다시 알파벳으로 바꿔준다.
zip([], [])을 이용해서 딕셔너리에 key와 value를 동시에 update시켜주었다.
