[C++] 백준 1969번: DNA

문제 링크

https://www.acmicpc.net/problem/1969

풀이 방법

DNA s1, s2, ..., sn가 주어져 있을 때 Hamming Distance의 합이 가장 작은 DNA s를 구해야 한다. 해당 문제의 핵심 Key Point는 입력된 문자열 s1,s2, ...., sn 똑같은 위치에 존재하는 알파벳 중 가장 많은 알파벳을 사전 순서대로 넣으면 해당 문자열 s를 구할 수 있다. 아래 예시를 참고하면 이해가 될 것이다.

TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

위 문자열에서 첫 번째 위치로 설명을 하면 T가 4개, A가 1개 이므로 T를 선택하면 된다. 이런 식으로 각 위치 별로 가장 많이 존재하는 알파벳을 하나 선택하면 TAAGATAC가 선택된다. 다만 알파벳의 개수가 같은 경우 A,C,G,T 의 사전 순서대로 먼저 선택하면 자연스럽게 사전 순으로 가장 앞서는 것을 출력한다.

위 설명과 아래 코드의 주석을 참고해서 해당 문제를 이해하자!

코드

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


int n, m;
char arr[1005][55];
vector<char> result;
int cntHammingDistanceSum;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;

    char alpha;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> alpha;
            arr[i][j] = alpha;
        }
    }


    // 문자열 s를 result vector에 담는다.
    for (int i = 0; i < m; i++) {
        int cntA = 0, cntC = 0, cntG = 0, cntT = 0;
        int maxAlpha = 0;
        for (int j = 0; j < n; j++) {
            if (arr[j][i] == 'A') cntA++;
            else if (arr[j][i] == 'C') cntC++;
            else if (arr[j][i] == 'G') cntG++;
            else if (arr[j][i] == 'T') cntT++;
        }
        maxAlpha = max(cntA, max(cntC, max(cntG, cntT)));

        // 사전순서 대로 분기 A,C,G,T
        if (maxAlpha == cntA) result.push_back('A');
        else if (maxAlpha == cntC) result.push_back('C');
        else if (maxAlpha == cntG) result.push_back('G');
        else if (maxAlpha == cntT) result.push_back('T');
    }

    //문자열 s 출력
    for (auto c : result) {
        cout << c;
    }
    cout << '\n';

    // Hamming Distance의 합을 구해서 출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (result[j] != arr[i][j]) cntHammingDistanceSum++;
        }
    }
    cout << cntHammingDistanceSum;
}