[BOJ] DNA 1969번 C++

 

문제

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가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

 

접근 방식

 

각 인덱스마다 가장 많이 나오는 뉴클레오티드로 문자열을 만들어 주면 된다

예를 들어 AAA, ATC, CTC가 있다면

0번째 인덱스는 A

1번째 인덱스는 T

2번째 인덱스는 C가 있으므로

최종 문자열은 ATC가 된다

 

map을 활용해 각 인덱스 자리에 가장 많이 나오는 뉴클레오티드 문자를 구해주었다

이때, 모두 동일하게 나올 수 있으므로 이를 사전순으로 앞서는 것을 구하기 위해

뉴클레오티드를 A,C,G,T로 정렬한 후 뒤에서 부터 반복문을 돌아주었다.

 

 

코드

 

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

int N,M, total = 0;
string ans;
vector<string> s;
map<char,int> m;
char dna[4] = {'A', 'C', 'G', 'T'};


int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>N>>M;
    for(int i=0; i<N; i++) {
        string x; cin>>x;
        s.push_back(x);
    }
    int idx = 0;
    while(true) {
        int freq = 0;
        char tmp;

        if(idx == M) break;

        for(int i=0; i<N; i++) {
            m[s[i][idx]]++;
        }

        for(int i=4; i>=0; i--) {
            if(freq <= m[dna[i]]) {
                freq = m[dna[i]];
                tmp = dna[i];
            }
        }

        ans += tmp;
        total += N - m[tmp];
        idx++;
        for(int i=0; i<4; i++) {
            m[dna[i]] = 0;
        }


    }
    cout<<ans<<'\n'<<total;
    
}