[BOJ:1696] DNA

Link : https://www.acmicpc.net/problem/1969

Note

문제를 정확히 읽자.

• 잘 못 읽은 문장

  • N개의 길이인 M인 DNA 등의 문장
  • S와 S1의 Hamming Distance등의 문장

• 구해야할 새로운 DNA s는 입력으로 주어진 DNA들의 각 위치 별로 가장 많이 등장한 뉴클레오티드로 구성하면 Hamming Distance 합이 최소가 되는 DNA s를 구할 수 있다.
  예를 들면 아래와 같은 입력이 주어 졌을 때 새로 구할 S의 첫 번째 뉴클레오티드를 T로 하면 3번째 "AAAGATCC" DNA에서만 첫 번째 자리에서 Hamming Distance값이 더해진다. 즉, 새로 구할 DNA는 주어진 DNA의 각 자리를 모두 확인해서 빈도수가 높은 뉴클레오티드로 채워주면 된다. 이때 각 자리별 뉴클레오티드의 최대 빈도수가 동일하면 알파벳 순서로 배치해야하므로 주의한다.

5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

Code

from itertools import product
import sys

input = sys.stdin.readline

n,m = map(int,input().split())
DNAs = []
for _ in range(n):
    DNAs.append(input().rstrip())

nucleotides = ["A","C","G","T"] #알파벳 순서로
DNA = ""
# DNA의 각 위치별로 가장 빈도수 높은 Nucleotide를 체크
for i in range(m):
    nucleotide_cnt = {"A":0,"C":0,"G":0,"T":0}
    for j in range(n):
        nucleotide_cnt[DNAs[j][i]] += 1

    nucleotide = max(nucleotide_cnt.values())

    for key in nucleotides:
        if nucleotide_cnt[key] == nucleotide:
            DNA += key
            break
cnt = 0
for i in range(n):
    for j in range(m):
        if DNA[j] != DNAs[i][j]:
            cnt += 1
print(DNA)
print(cnt)