[1969 번] DNA

www.acmicpc.net/problem/1969

1969번: DNA

이 문제는 주어진 DNA들에대해 Hamming Distance의 합이 가장 작은 DNA하나를 찾고, 그, Hamming  Distance의 합을 구하는 문제입니다.

*Hamming Distance : 두 DNA가 있을 때 각 위치의  뉴클오티드 문자가 다른 것의 개수

 

입력받은 DNA들과의 Hamming Distance 합이 최소가 되기 위해서는 각 열 별로 빈도가 가장 높은 문자를 찾으면 그 DNA는 최소의  Hamming distance를 가질 수 있습니다.

주의할 점은 답이 여러개일 경우 사전순으로 출력하라 했으므로 A -> C -> G  -> T 순으로 체크해야한다는 것입니다.

 

예제1

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    vector<string> v;
    int dna[5] = {0,};
    int max_num;
    int distance = 0;
    string answer = "";

    int N, M;
    cin>>N>>M;

    for(int i = 0; i<N; i++){
        string s;
        cin>>s;
        v.push_back(s);
    }

    for(int i = 0; i<M; i++){
        for(int j = 0; j<N; j++){
            //count
            if(v[j][i]=='A'){
                dna[0] += 1;
            }
            else if(v[j][i]=='C'){
                dna[1] += 1;
            }
            else if(v[j][i]=='G'){
                dna[2] += 1;
            }
            else if(v[j][i]=='T'){
                dna[3] += 1;
            }
        }

        //find max_num
        max_num = max(max(max(dna[0], dna[1]), dna[2]), dna[3]);

        if(dna[0]==max_num){
            answer += 'A';
        }
        else if(dna[1]==max_num){
            answer += 'C';
        }
        else if(dna[2]==max_num){
            answer += 'G';
        }
        else if(dna[3]==max_num){
            answer += 'T';
        }

        //reset
        for(int k = 0; k<4; k++){
            dna[k] = 0;
        }
    }

    //Hamming Distance 계산
    for(int i = 0; i<N; i++){
        for(int k = 0; k<M; k++){
            if(v[i][k]!=answer[k]){
                distance += 1;
            }
        }
    }
    cout<< answer << "\n"<< distance;
}