본문 바로가기

Algorithm Problems/구현

[백준/Python] 1969번: DNA

문제

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

 

1969번: DNA

DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오

www.acmicpc.net


문제 요약

길이가 M인 DNA 뉴클레오티드 문자열 N개를 입력 받고, 각 문자열에 대해 Hamming Distance의 합이 가장 작은 DNA와 Hamming Distance의 합을 출력한다.

 

Hamming Distance란 길이가 같은 두 DNA가 있을 때, 각 위치의 뉴클레오티드 문자가 다른 것의 개수이다.

 

ex) TATGATAC와 TAAGCTAC의 세 번째 문자와 다섯 번째 문자가 다르므로, Hamming Distance는 2이다.


코드

n, m = map(int, input().split())

# 각 문자열들의 i번째 인덱스에 어떤 문자가 몇 번 등장했는지 저장하는 2차원 딕셔너리
arr = [{} for _ in range(m)]

# 딕셔너리에 각 DNA 뉴클레오티드 문자열의 정보 저장
for _ in range(n):
    string = input()
    for i in range(m):
        if string[i] not in arr[i].keys():
            arr[i][string[i]] = 1
        else:
            arr[i][string[i]] += 1
    

res = "" # 결과 DNA의 뉴클레오티드 문자열
res_cnt = 0 # 결과 DNA와 다른 DNA간의 Hamming Distance의 합

# arr[i] 딕셔너리에서 가장 Value값(등장횟수)이 큰 문자를 구하고, 그 문자와 디른 문자가 몇 개 있는지 저장
for i in range(m):
    ans = ""
    cnt = 0
    for key in arr[i].keys():
        if cnt < arr[i][key] or (cnt == arr[i][key] and key < ans):
            cnt = arr[i][key]
            ans = key
                    
    res_cnt += (n - cnt)
    res += ans
    
print(res)
print(res_cnt)

코드 설명

1. 각 DNA 뉴클레오티드의 i번째 문자들 중 어떤 문자가 몇 번 등장했는지 저장하는 2차원 딕셔너리 arr를 생성한다.

 

2. i번째 딕셔너리에서 가장 등장횟수가 많은 문자를 찾고, 그 문자와 다른 문자는 몇 번 등장했는지 확인한다.