[백준,c++] 1969번 - DNA

문제

1969번: DNA

 

코드

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N, M; cin>>N>>M;
    vector<string>v;
    string dna;
    int hamming_distance_cnt = 0;
    
    for(int i=0; i<N; i++){
        string inp; cin>>inp;
        v.push_back(inp);
    }
    
    for(int i=0; i<M; i++){
        map<char,int> cnt;
        int max_cnt = -1;
        char max_char = 'Z';
        for(int k=0; k<N; k++){
            cnt[v[k][i]]++;
            if(max_cnt<cnt[v[k][i]]){
                max_cnt = cnt[v[k][i]];
                max_char = v[k][i];
            }
            else if(max_cnt==cnt[v[k][i]]){
                max_char = min(max_char, v[k][i]);
            }
        }
        dna += max_char;
    }
    
    for(int i=0; i<M; i++){
        for(int k=0; k<N; k++){
            if(v[k][i]!=dna[i]) hamming_distance_cnt++;
        }
    }
    cout<<dna<<'\n'<<hamming_distance_cnt;
}

 

풀이

각 DNA에서 가장 빈도수가 많은 알파벳을 찾습니다. 만약 빈도수가 같다면 사전 순으로 우선인 알파벳을 뽑아냅니다.

Hamming Distance는 뽑아낸 알파벳들과 비교했을 때 다를 경우의 알파벳의 개수를 전부 세어 주면 됩니다.