[BOJ] 1969. DNA ✔

SuLee·2021년 7월 14일
0

BOJ

목록 보기
17/67

1969. DNA

1. 문제

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,...,sns_1, s_2, ..., s_n가 주어져 있을 때 Hamming Distance의 합이 가장 작은 DNA ss를 구하는 것이다. 즉, sss1s_1의 Hamming Distance + sss2s_2의 Hamming Distance + sss3s_3의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.

2. 입력

첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.

3. 출력

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

4. 풀이

Python

from collections import Counter

N, M = map(int, input().split())
dna = [input() for _ in range(N)]

# 각 자리의 알파벳 중 가장 많이 나오는 것을 선택
result = ''
for i in range(M):
    li = sorted([dna[j][i] for j in range(N)])
    result += Counter(li).most_common(1)[0][0]
    
print(result)

# 해밍 거리 계산
cnt = 0
for i in range(M):
    for j in range(N):
        if result[i] != dna[j][i]:
            cnt += 1
            
print(cnt)

C++

using namespace std;
#include <bits/stdc++.h>

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    vector<string> strs(N);
    for (string& str : strs) cin >> str;
    
    string result("");
    int HD(0);
    for (int i = 0; i < M; ++i)
    {
        int maxCount(0), alphabet[26] {0, };
        char ch;
        
        // 각 자리에서 어떤 알파벳이 얼마나 나왔는지 기록
        for (string& str : strs) ++alphabet[str[i] - 'A'];
        
		// 각 자리마다 제일 많이 나온 알파벳 찾기
        for (int i = 0; i < 26; ++i)
        {
        	if (alphabet[i] > maxCount) ch = i + 'A', maxCount = alphabet[i];
        }
        
        result += ch;
        // N - maxCount 개의 배열은 다른 알파벳이 나왔으므로 그만큼을 Hamming Distance에 더함
        HD += N - maxCount;
    }
    
    cout << result << "\n" << HD;
}

0개의 댓글