[Baekjoon/C++] 1969번 - DNA

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

 

---

풀이

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

int N, M;
string arr[1001];
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++) cin >> arr[i];

    int mn = 0;
    string result = "";

    for (int i = 0; i < M; i++) {
        map<char, int> cnt;

        for (int j = 0; j < N; j++) cnt[arr[j][i]]++;

        int idx = 0;
        for (int j = 1; j < 4; j++) {
            if (cnt[dna[j]] > cnt[dna[idx]]) idx = j;
        }

        result += dna[idx];
        mn += (N - cnt[dna[idx]]);
    }

    cout << result << '\n' << mn << '\n';

    return 0;
}

 

i | j	0	1	2	3	4	5	6	7
0	T	A	T	G	A	T	A	C
1	T	A	A	G	C	T	A	C
2	A	A	A	G	A	T	C	C
3	T	G	A	G	A	T	A	C
4	T	A	A	G	A	T	G	T
result	T	A	A	G	A	T	A	C

 N개의 문자열의 i번째 자리의 문자 중 가장 빈도가 많은 것을 선택하여 문자열을 구성해야 Hamming Distance의 합이 가장 적은 DNA를 만들 수 있다.

i번째 칸의 Hamming Distance은 선택한 문자가 등장한 횟수를 제외한 수와 같다.