백준 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보다 작거나 같은 자연수이다.

 

 

출력

 

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

 

 

이 문제는 주어진 DNA들과의 Hamming Distance 합이 가장 최소가 되는 DNA를 구하면 된다. 

문제를 푸는 방법은 간단하다. 주어진 DNA들의 각 위치마다 뉴클오티드 문자를 세서, 그 개수가 가장 많은 것들을 연결하면 된다. 이때 사전순으로 출력하므로 뉴클오티드 문자의 수가 같을 경우에는 가장 알파벳 순서가 빠른 것을 선택한다. 

Hamming Distance 합은 DNA의 총 개수에서 선택한 뉴클오티드 문자의 개수를 뺀 것들의 합이 된다. 

 

 

코드

 

#include <iostream>
#include <string>
using namespace std;

int n, m;
string DNA[1000];

int max_num(int a, int c, int g, int t){
    int max;

    max=(a>=c)?a:c;
    max=(max>=g)?max:g;
    max=(max>=t)?max:t;
    
    return max;
}

void hamming_distance(){
    int cnt=0;
    string dna="";
    
    for(int i=0; i<m; i++){
        int a=0, c=0, g=0, t=0;
        for(int j=0; j<n; j++){
            switch(DNA[j][i]){
                case 'A':
                    a++;
                    break;
                case 'C':
                    c++;
                    break;
                case 'G':
                    g++;
                    break;
                case 'T':
                    t++;
                    break;
            }
        }
        
        int max=max_num(a, c, g, t);
        
        if(max==a) dna+='A';
        else if(max==c) dna+='C';
        else if(max==g) dna+='G';
        else dna+='T';
        
        cnt+=(n-max);

    }
    
    cout<<dna<<'\n'<<cnt;
}

int main(){
    cin>>n>>m;
    for(int i=0; i<n; i++)
        cin>>DNA[i];
    
    hamming_distance();
}