[백준 1969번] 파이썬 - DNA

백준 1969 - DNA

시간 제한 2초, 메모리 제한 128MB

# 조건

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

# 접근 방법

• 처음에 문제를 똑바로 읽지 않아 나올 수 있는 단어의 첫 글자가 4개란 사실을 놓쳤다.
• 우선 입력받는 DNA의 문자열을 WORDS에 저장해주고 각 자리에서 나오는 알파벳의 개수를 세어줄 리스트 count를 [M][26]의 크기로 만들어주었다.
• 이후 각 자리의 알파벳을 보기 편하게 해주기 위하여 ZIP을 활용하여 1, 2, 3 ... 번째 자리의 알파벳끼리 묶어주었다.
• ZIP을 사용하여 생성된 리스트를 순회하며 아스키 코드 변환 된 수 - 65에 +=1 을 하여 개수를 세어주었다.
• 이후 target과 result 변수를 만든 후, 각 자리에서 가장 많이 나온 알파벳을 target에 더해주고, N - 가장 많이 나온 알파벳의 수를 result에 더해주었다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N, M = map(int, input().split())  
words = [list(map(str, input().strip())) for _ in range(N)]  
count = [[0] * 26 for _ in range(M)]  
words = list(zip(*words))  
for idx, word in enumerate(words):  
    for w in word:  
        count[idx][ord(w) - 65] +=1  

target = ''  
result = 0  
for i in range(M):  
    cnt = 0  
    temp = ''  
    for j in range(26):  
        if count[i][j] > cnt:  
            cnt = count[i][j]  
            temp = chr(j+65)  
    target += temp  
    result += N - cnt  
print(target)  
print(result)