[C++] 백준 1969번:DNA

문제링크

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

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

 

풀이

Hamming Distance의 합이 최소가 되기 위해서는 각 위치의 알파벳을 가장 많이 나온 알파벳으로 넣어주면 된다.

ex)

T A T G A T A C

T A A G C T A C

A A A G A T C C

T G A G A T A C

T A A G A T G T

 

1 자리 : A-1 C-0 G-0 T-4 최다-T

2 자리 : A-4 C-0 G-1 T-0 최다-A

3 자리 : A-4 C-0 G-0 T-1 최다-A

4 자리 : A-0 C-0 G-5 T-0 최다-G

5 자리 : A-4 C-1 G-0 T-0 최다-A

6 자리 : A-0 C-0 G-0 T-5 최다-T

7 자리 : A-3 C-1 G-1 T-0 최다-A

8 자리 : A-0 C-4 G-0 T-1 최다-C

->TAAGATAC가 된다.

 

각 문자열마다 같은 자리 위치의 알파벳을 비교하고 가장 많이 나온 알파벳을 찾아 차례대로 추가해준다.

-> 크기 4짜리 배열을 만들어주고 순서대로 A,C,G,T가 나온 횟수를 넣어준다.

Hamming Distance의 합이 최소인 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력해야 하므로 1-1에서 A,C,G,T의 순서대로 세어줘야 한다. (앞부터 비교하면 다른 처리를 해주지 않아도 사전순으로 알파벳이 정해지기 때문에)

ex)

4 4

GAGT

GACT

CAGT

CGTA

G와 C모두 2번 씩 나왔지만 A,C,G,T의 순서대로 큰 값을 찾기 때문에 C가 출력된다.

CAGT

6

 

코드

#include <iostream>
#include <string>
using namespace std;
 
int n, m;
string arr[1001];
string res;
 
int main() {
    cin >> n >> m;
 
    // 입력
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    // 각 문자열의 자리수마다 가장 많이 나온 알파벳 검색
    for (int i = 0; i < m; i++) {
        int cnt[4] = { 0 };        // 알파벳 나온 횟수 저장
        int maxindex = 0;        // 최대 횟수의 index 저장
        for (int j = 0; j < n; j++) {
 
 
            if (arr[j][i] == 'A') {
                cnt[0]++;
            }
            else if (arr[j][i] == 'C') {
                cnt[1]++;
            }
            else if (arr[j][i] == 'G') {
                cnt[2]++;
            }
            else if (arr[j][i] == 'T') {
                cnt[3]++;
            }
        }
 
        // 최대 횟수 index 검색, 사전순 처리 완료
        for (int a = 1; a < 4; a++) {
            if (cnt[a] > cnt[maxindex]) {
                maxindex = a;
            }
        }
 
        if (maxindex == 0) {
            res = res + "A";
        }
        else if (maxindex == 1) {
            res = res + "C";
        }
        else if (maxindex == 2) {
            res = res + "G";
        }
        else if (maxindex == 3) {
            res = res + "T";
        }
    }
    cout << res << '\n';
 
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] != res[j]) {
                count++;
            }
        }
    }
    cout << count;
}

 

메모

.