[BOJ] 1969번: DNA

https://www.acmicpc.net/problem/1969

---

문제

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 ... 의 합이 최소가 된다는 의미이다.

 

 

풀이

우선 2차원 배열로 입력받은 후, 각각의 열을 비교해야겠다는 생각을 했다. 

#틀린 코드
from collections import defaultdict

s = ''
n, m = map(int, input().split())
DNA = [list(input()) for _ in range(n)] 

for j in range(m):
    dict = defaultdict(int)
    
    for i in range(n):
        dict[DNA[i][j]] += 1
    
    max_cnt = max(dict.values())
    
    for nu in ["A", "T", "G", "C"]:
        if dict[nu] == max_cnt:
            s += nu
            break

hamming_dist = 0
for i in range(n):
    for j in range(m):
        if DNA[i][j] != s[j]:
            hamming_dist += 1

print(s)
print(hamming_dist)

 

각각의 뉴클레오티드가 몇개인지를 어떻게 세지? 라고 생각하던 중 어제 배운 defaultdict이 생각나 적용해봤다. 

어찌저찌 예제 테스트케이스를 통과한 후... 제출하니 오답이랜다...

좋은 습관은 아닌 거 같지만 질문 게시판에 들어가서 반례를 살펴봤다.

그런데 생각해보니 "그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다." 를 무시하고 있었던 것...! 왜 항상 이런 디테일들을 놓치는지 모르겠다.😰 심지어 저런 조건이 있는 것을 인지한 상태에서... 아무생각 없이 티딕티딕 짰다. 완저니 바멍~ 바보멍청이

 

여튼 최종 코드는 다음과 같다

from collections import defaultdict

s = ''
n, m = map(int, input().split())
DNA = [list(input()) for _ in range(n)] 

for j in range(m):
    dict = defaultdict(int)
    
    for i in range(n):
        dict[DNA[i][j]] += 1
    
    max_cnt = max(dict.values()) #가장 많은 횟수
    
    for nu in ["A", "C", "G", "T"]: #수정된 부분: 알파벳 순으로 살피기
        if dict[nu] == max_cnt:
            s += nu
            break

hamming_dist = 0
for i in range(n):
    for j in range(m):
        if DNA[i][j] != s[j]:
            hamming_dist += 1

print(s)
print(hamming_dist)

 

1. 우선 defaultdict을 사용하기 위한 모듈을 불러온다.

2. 가장 작은 Hamming distance를 가지는 문자열을 저장할 s를 초기화한다.

3. n, m을 입력받고, s1, s2...를 이차원 배열로 입력받는다.

4. 열끼리 비교한다. 열이 바뀔 때마다 defaultdict을 초기화하며, 각 열들의 뉴클레오타이드의 개수를 딕셔너리 형태로 저장한다.

5. 가장 큰 횟수를 가지는 뉴클레오타이드를 s에 저장한다.

6. hamming distance를 계산한다.

출력하면 끝!