BOJ 1969

Input

첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다.

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

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
s = [input().upper() for _ in range(n)]

Brute Force

hamming distance가 작다 = string.charAt(index)가 가장 빈번한 글자를 택하면 됨

원래는 dict 를 활용해서 풀었는데 주어진 케이스는 모두 맞았지만 틀렸다고 해서 배열에 ord 를 사용하는 코드로 바꿨더니 맞았다. 뭐가 다른 거지, 히든 케이스가 뭐였을까

기존 코드

count = [{'A': 0, 'T': 0, 'G': 0, 'C': 0} for _ in range(m)]

		count[j][now] += 1

for i in range(m):
  ret += max(count[i].items(), key=operator.itemgetter(1))[0]

변경 코드

count = [[0]*26 for _ in range(m)]

    count[j][ord(now)-65] += 1

for i in range(m):
  ret += chr(count[i].index(max(count[i])) + 65)

Output

첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고,

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

for i in range(n):
  word = s[i]

  for j in range(m):
    if word[j] != ret[j]:
      ans += 1

print(ret)
print(ans)