[백준 /Python] 1969번: DNA

https://velog.io/@jay6768/BOJ-Python-1969-DNA

[BOJ / Python] 1969 - DNA

 

Intro

DNA가 무엇인지, Hamming Distance가 무엇인지 구구절절 설명해놓아 어려운 듯했지만 주어진 입력 문자열들에서 자리마다 가장 자주 등장하는 문자를 모두 더해 새로운 문자를 만들어내는 방식으로 풀 수 있다.

Solution

1. n개의 문자열을 입력한다.
2. m회 반복하며 그 내부에서 모든 DNA를 자리마다 순회하며 등장하는 문자의 개수를 센다. key를 문자, value를 개수로 하여 딕셔너리 변수 count에 저장한다.
3. 반복마다 가장 자주 등장한, 즉 count에서 value가 가장 큰 문자 key가 문자열 변수 result에 더해지며 정답을 만들어나간다. 이때 count 변수를 value 숫자 내림차순, key 문자(알파벳) 오름차순으로 정렬하여 조건에 맞는 문자를 찾을 수 있게 한다.
4. result 생성이 끝난 후 모든 DNA를 m번씩 순회하며 각각의 DNA를 result와 자리마다 비교하여 다른 문자의 개수(hamming distance)를 합하여 total에 저장한다.

Code

from sys import stdin
input = stdin.readline

def main():
	n, m = map(int, input().split())
	dna = [input() for _ in range(n)]
	result = ""
	for i in range(m):
		count = {}
		for d in dna:
			if d[i] in count:
				count[d[i]] += 1
			else:
				count[d[i]] = 1
		result += sorted(count, key=lambda x: (-count[x], x))[0]

	total = 0
	for j in range(n):
		for k in range(m):
			if result[k] != dna[j][k]:
				total += 1

	print(f"{result}\n{total}")

main()