[백준 1969번 문제, Python3] 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가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

---

코드

input_count, input_length = map(int, input().split(' '))    # 첫번째 줄 입력
inputs = [list(input()) for _ in range(input_count)]    # 두번쨰 줄 부터 DNA 입력 받고 리스트에 추가
inputs = list(zip(*inputs))    # 입력 받은 DNA 리스트를 전치함

answer_dna = []
answer_distance = 0

for i, v in enumerate(inputs):
    inputs[i] = sorted(list(v))    # 리스트를 사전순으로 정렬함
    my_dict = dict()    # 키 = 뉴클레오티드 문자, 값 = 빈도수 형태로 딕셔너리를 만들거임

    for j in inputs[i]:
        my_dict[j] = my_dict.get(j, 0) + 1    # 빈도수 체크

    min_dna = max(my_dict, key=my_dict.get)    # 최다 빈도수의 뉴클레오티드의 개수
    answer_dna.append(min_dna)    # 정답 dna 리스트에 추가

    answer_distance = answer_distance + len(inputs[i]) - inputs[i].count(min_dna)    # dna 길이 - 최대 빈도수의 뉴클레오티드 개수

answer_dna = ''.join(answer_dna)    # dna 리스트를 문자열로 변환
print(f'{answer_dna}\n{answer_distance}')

---

해결

백준 문제 설명이 정말 이해하기가 어려워서 처음부터 문제를 보자면

다음과 같은 dna가 주어지면

각 열들의 행값들을 비교해서 최다 빈도수로 dna 문자열을 만들고 서로 다른 dna 즉 해밍거리를 구해야한다

 

 

세로로 AAAGA 에서 가장 많은 빈도를 가진 문자는 A 그리고 다른 문자는 G 하나 뿐이니 해밍 거리는 1

또한 세로로 AACAG 인경우 가장 많은 빈도를 가진 문자는 A 그리고 다른 문자는 C, G이니 해밍 거리는 2

 

게다가 해밍거리가 같은 경우 사전순으로 DNA 문자열을 만들어야 하기 때문에 정렬을 먼저 해줘야하는데

그냥 정렬하면 행, 열의 순서가 흐트러지므로 전치를 해줘야한다

 

파이썬에서는 전치를 정말 쉽게 zip 메서드를 사용하면 된다

---

참고

링크