문제
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번째 딕셔너리에서 가장 등장횟수가 많은 문자를 찾고, 그 문자와 다른 문자는 몇 번 등장했는지 확인한다.
'Algorithm Problems > 구현' 카테고리의 다른 글
[백준/Python] 17300번: 패턴 (1) | 2024.01.06 |
---|---|
[백준/Python] 23349번: 졸업 사진 (0) | 2024.01.01 |
[백준/Python] 1408번: 24 (2) | 2023.10.10 |
[백준/python] 2852번: NBA 농구 (2) | 2023.08.01 |
[백준/python] 2999번: 비밀 이메일 (2) | 2023.07.24 |