[백준][Python] 1969. DNA

Silver Ⅳ 🔗1969. DNA

📝문제 요약

문제 설명

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가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

✏️문제 풀이

• DNA의 수 n과 문자열의 길이 m을 입력
• n개의 DNA을 dna_list에 저장
• m 번 반복하여 DNA의 각 뉴클레오티드 확인
  • dna_cnt ⇒ [0, 0, 0, 0]으로 초기화 : ['A', 'C', 'G', 'T'] 각각의 개수 저장
  • 각 DNA의 i번째 위치의 문자를 카운팅
• 가장 많이 등장한 문자의 개수와 인덱스를 구함
• 가장 많이 등장한 문자를 결과 DNA에 추가
• 현재 자릿수에서 다른 DNA들과 일치하지 않는 개수를 빼서 total_hamming_distance 에 더해줌
• 최종 결과 출력
  • Hamming Distance가 가장 작은 대표 DNA : answer
  • 총 Hamming Distance 값 : total_hamming_distance

코드와 함께 보는 풀이

# n: DNA 개수, m: DNA 길이
n, m = map(int, input().split())

# DNA 목록 입력 받기
dna_list = [input() for _ in range(n)]

# 결과 DNA 문자열과 Hamming 거리 총합 변수 초기화
answer = ''
total_hamming_distance = 0

# 뉴클레오타이드 리스트
nucleotide = ['A', 'C', 'G', 'T']

# 각 자리마다 가장 많이 등장한 뉴클레오타이드를 찾기
for i in range(m):
		# A, C, G, T 각각의 개수를 저장하는 리스트 초기화
    dna_cnt = [0] * 4 

    # 각 DNA의 i번째 위치의 문자 개수 세기
    for dna in dna_list:
        dna_cnt[nucleotide.index(dna[i])] += 1

    # 가장 많이 등장한 문자의 개수와 인덱스를 구함
    max_cnt = max(dna_cnt)
    max_idx = dna_cnt.index(max_cnt)

    # 가장 많이 등장한 문자를 결과 DNA에 추가
    answer += nucleotide[max_idx]

    # Hamming Distance: n개 중에서 max_cnt개만 일치하므로 나머지는 다름
    total_hamming_distance += (n - max_cnt)

# Hamming Distance가 가장 작은 대표 DNA 출력
print(answer)
     
# 총 Hamming Distance 값 출력
print(total_hamming_distance)

💯제출 코드

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

answer = ''
total_hamming_distance = 0
nucleotide = ['A', 'C', 'G', 'T']

for i in range(m):
    dna_cnt = [0] * 4
    for dna in dna_list:
        dna_cnt[nucleotide.index(dna[i])] += 1

    max_cnt = max(dna_cnt)
    max_idx = dna_cnt.index(max_cnt)
    answer += nucleotide[max_idx]
    total_hamming_distance += (n - max_cnt)

print(answer)
print(total_hamming_distance)