[Python 알고리즘] 백준 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보다 작거나 같은 자연수이다.

# Case 1
5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT


# Case 2
4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA


# Case 3
6 10
ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA

출력

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

# Case 1
TAAGATAC
7


# Case 2
ACGTACGTAA
6


# Case 3
AAGTTACCAA
12

내가 제출한 풀이 - 정답

1차시도 (실패)

import operator
import sys
from collections import defaultdict

n, m = list(map(int, sys.stdin.readline().strip().split()))
dna_list = [sys.stdin.readline().strip() for _ in range(n)]
res_cnt = 0
min_dict = defaultdict(int)

for i in range(0, m):
    cnt = defaultdict(int)

    for j in range(0, len(dna_list)):
        cnt[dna_list[j][i]] += 1

    max_str = sorted(cnt.items(), key=operator.itemgetter(1), reverse=True)[0][0]

    for j in range(0, len(dna_list)):
        if max_str not in dna_list[j][i]:
            res_cnt += 1
            min_dict[dna_list[j]] += 1

for i in range(0, len(dna_list)):
    if dna_list[i] not in min_dict.keys():
        min_dict[dna_list[i]] = 0

min_list = list(min_dict.items())
min_list.sort(key=lambda x: (x[1], x[0]))

print(min_list[0][0])
print(res_cnt)

defaultdict를 사용하여 문제를 풀이하다가 만약 아무것도 해당하지 않을 때는 0으로 출력해야하는데 카운트가 되어 1로 출력돼서 반례가 생겼고, 뉴클레오티드 문자열이 고정되어 있기 때문에 굳이 defaultdict를 하지 않아도 된다고 생각해 다시 새로 짜기로 했다.

 

2차시도 (104ms)

import sys
from collections import defaultdict

n, m = list(map(int, sys.stdin.readline().strip().split()))
dna_list = [sys.stdin.readline().strip() for _ in range(n)]
res_cnt = 0
res_str = ''

for i in range(0, m):
    # A C G T 순
    nucleotide_list = [0, 0, 0, 0]

    for j in range(0, n):
        if dna_list[j][i] == 'A':
            nucleotide_list[0] += 1
        elif dna_list[j][i] == 'C':
            nucleotide_list[1] += 1
        elif dna_list[j][i] == 'G':
            nucleotide_list[2] += 1
        elif dna_list[j][i] == 'T':
            nucleotide_list[3] += 1

    max_idx = nucleotide_list.index(max(nucleotide_list))

    if max_idx == 0:
        res_str += 'A'
        res_cnt += nucleotide_list[1] + nucleotide_list[2] + nucleotide_list[3]
    elif max_idx == 1:
        res_str += 'C'
        res_cnt += nucleotide_list[0] + nucleotide_list[2] + nucleotide_list[3]
    elif max_idx == 2:
        res_str += 'G'
        res_cnt += nucleotide_list[0] + nucleotide_list[1] + nucleotide_list[3]
    elif max_idx == 3:
        res_str += 'T'
        res_cnt += nucleotide_list[0] + nucleotide_list[1] + nucleotide_list[2]

print(res_str)
print(res_cnt)

dict를 사용하지 않고 리스트를 사용하여 풀어냈다.

 

문제 해설

이번 문제는 보자마자 브루트 포스라는 것을 알 수 있었고, 난 문제 자체를 이해하기가 어려워 검색을 통해 이해를 했다.

각각 문자열 자리마다 가장 많은 문자를 가져와 그 문자와 다른 개수를 얻어내면 된다.

문자와 다른 개수의 합이 Hamming Distance이며, 결과를 도출한 DNA와 가장 일치하는 것이 가장 작은 DNA가 되는 것이다.

 

# A C G T 순
nucleotide_list = [0, 0, 0, 0]

for j in range(0, n):
    if dna_list[j][i] == 'A':
        nucleotide_list[0] += 1
    elif dna_list[j][i] == 'C':
        nucleotide_list[1] += 1
    elif dna_list[j][i] == 'G':
        nucleotide_list[2] += 1
    elif dna_list[j][i] == 'T':
        nucleotide_list[3] += 1

뉴클리오티드 문자는 A, C, G, T 고정이기 때문에 가능한 코드이기도 하다.

0번째 인덱스는 A, 1번째 인덱스는 C, 2번째 인덱스는 G, 3번째 인덱스는 T라고 가정하고 리스트를 만들어 냈다.

해당 문자열이 나왔다면 카운트를 1씩 올려준다.

 

# 가장 많은 뉴클레오티드 문자를 가져옴
max_idx = nucleotide_list.index(max(nucleotide_list))

if max_idx == 0:
    res_str += 'A'
    res_cnt += nucleotide_list[1] + nucleotide_list[2] + nucleotide_list[3]
elif max_idx == 1:
    res_str += 'C'
    res_cnt += nucleotide_list[0] + nucleotide_list[2] + nucleotide_list[3]
elif max_idx == 2:
    res_str += 'G'
    res_cnt += nucleotide_list[0] + nucleotide_list[1] + nucleotide_list[3]
elif max_idx == 3:
    res_str += 'T'
    res_cnt += nucleotide_list[0] + nucleotide_list[1] + nucleotide_list[2]

 

1. max와 index 함수를 이용해 가장 많이 포함된 뉴클레오티드 문자를 가져온다.
2. 해당 인덱스와 일치하다면 뉴클레오티드 문자를 추가하고, 나머지 카운트를 더하여 Hamming Distance를 만들어준다.

이번 문제는 문자열이 고정되어 있기 때문에 쉬운 문제였다.

 

TIP

defaultDict

from collections import defaultdict

test_dict = defaultdict(int)
test_dict['test'] += 1

# test_dict = { 'test': 1 }

이렇게 사용하는 과정인데 이것이 뭐가 좋다는 거지?라고 생각하는 사람들이 있을 것이다.

첫 번째는 defaultdict()의 인자로 주어진 자료형은 dictionary의 초깃값으로 지정될 수 있다.

 

두 번째는 다음과 같다.

test_dict = dict()
test_dict['test'] += 1

# KeyError: 'test'

기본적인 dict를 사용하면 'test' key로 접근을 할라하면 해당 키가 없기 때문에 KeyError가 발생하게 된다.

하지만, defaultdict를 사용하면 없는 key에 접근해도 defaultdict()의 초깃값을 따라 새롭게 생성해준다.

 

만약, 문자열이 'A', 'C', 'G', 'T'로 고정되어 있지 않았다면 defaultdict를 통해 풀어나갈 수 있었을 것이다.