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

Solved.ac 레벨

실버 V

풀이

#include <bits/stdc++.h>

using namespace std;

int n, m;
int dnaCnt[51][4];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    
    for(int i = 0; i < n; i++){
        string gene;
        cin >> gene;

        for(int j = 0; j < m; j++){
            switch (gene[j]){
                case 'A':
                    dnaCnt[j][0]++;
                    break;
                case 'C':
                    dnaCnt[j][1]++;
                    break;
                case 'G':
                    dnaCnt[j][2]++;
                    break;
                case 'T':
                    dnaCnt[j][3]++;
                    break;
            }
        }
    }

    string ans = "";
    int ansCnt = 0;

    for(int i = 0; i < m; i++){
        int maxIdx = 0, maxCnt = 0;

        for(int j = 0; j < 4; j++){
            if(dnaCnt[i][j] > maxCnt){
                maxCnt = dnaCnt[i][j];
                maxIdx = j;
            }
        }
        ansCnt += (n - maxCnt);

        switch (maxIdx)
        {
        case 0:
            ans += 'A';
            break;
        case 1:
            ans += 'C';
            break;
        case 2:
            ans += 'G';
            break;
        case 3:
            ans += 'T';
            break;
        }
    }

    cout << ans << "\n";
    cout << ansCnt << "\n";

    
    return 0;
}

문제 자체를 이해하는데에 굉장히 오랜 시간이 걸렸다... 그게 뭔데요... 무서워잉~

A, C, G, T 중 가장 많이 나온 뉴클레오티드의 개수를 구할 때 maxCnt = *max_element(dnaCnt[i], dnaCnt[i] + 4); 로 풀어도 답은 동일하게 나오는데 틀려서 애 좀 먹었다.

 

로직 자체를 구현하는 데에 있어서는 아래 블로그의 도움을 많이 받았다. 코드가 거의 동일할 정도.

이 자리를 빌어 감사하다는 말씀 드리고 싶다.

백준 1969번 DNA

 

1969번: DNA