📝 문제
💡 DNA란 어떤 유전물질을 구성하는 분자이다.
이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다.
우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오티드의 첫글자를 따서 표현한다.
만약에 Thymine-Adenine-Adenine로 이루어진 DNA가 있다고 하면, “TAA”로 표현할 수 있다.
그리고 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 + ... 의 합이 최소가 된다는 의미이다.
⚙️ 입력 : 첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다.
그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다.
N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.
⚙️ 출력 : 첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고,
둘째 줄에는 그 Hamming Distance의 합을 출력하시오.
그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.
1969번: DNA
DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오
www.acmicpc.net
✅ 풀이
n, m = map(int, input().split())
li = []
answer = ''
cnt = 0
for i in range(n):
li.append(input())
for i in range(m):
dict = {'A':0, 'C':0, 'G':0, 'T':0}
for item in li:
dict[item[i]] += 1
s = [k for k, v in dict.items() if v == max(dict.values())]
answer += s[0]
cnt += (sum(dict.values()) - max(dict.values()))
print(answer)
print(cnt)💡 모든 단어들과의 Hamming Distance 합을 최소화하는 단어를 찾기 위해서는,
단어 각 자리별로 가장 많이 나온 글자를 가지도록 하면 된다.
따라서 각 자리별로 A, C, G, T의 갯수를 세주었고,
이미 사전 순으로 갯수를 세었으므로 빈도가 동일해도 0번째 원소를 가져오면 된다.
Hamming 거리의 합의 경우, 각 자리로 결정된 글자를 제외한 글자들의 빈도 합을 구하면 된다.
