[Greedy] 1969번 DNA

1969번 DNA

 

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

 

문제

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개의 길이가 같은 DNA가 주어져 있을 때(이 DNA를 a1a2a3a4...이라고 하자) Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 a1의 Hamming Distance + s와 a2의 Hamming Distance + s와 a3의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.

 

입력

첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

 

예제 입력

5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA

6 10
ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA

 

예제 출력

TAAGATAC
7

ACGTACGTAA
6

AAGTTACCAA
12

 

해결방법

Greedy Algorithm 유형의 문제이다

우연히 솔루션을 봐버려서.... 흑 반성하자!!

 

 

⭐️ 솔루션 ⭐️

각 자리별로 문자의 횟수를 카운트하여 가장 많이 등장한 문자를 선택한다

이 때, 같은 카운트를 가진 경우는 사전순으로 정렬해야하기 때문에 cmp 함수를 잘 구현해야한다!!

 

시간 복잡도

각 DNA의 열에 대해 모든 행을 탐색한다 (n * m)

또한 이 과정에서 정렬을 수행하고 (k log k) , 해밍거리를 계산한다 (3)

따라서 전체 시간복잡도는 O(n * m * k log k) 가 나오게 된다

 

 

 

소스코드

문제 해결 시간 : 50m

메모리 : 2036 KB

시간 : 0 ms

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct code {
    char ch;
    int cnt;
    
    code() { }
    code(char _ch,int _cnt) : ch(_ch),cnt(_cnt) { }
};

bool cmp (code &c1, code &c2){
    if(c1.cnt == c2.cnt){
        return c1.ch < c2.ch;
    }else{
        return c1.cnt > c2.cnt;
    }
}

int n,m,cnt;
char dna[1001][51];
string ans = "";

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> dna[i][j];
        }
    }
    
    // 1열부터 각 행을 탐색해 가장 많이 나온 문자가 DNA 를 구성함
    for(int j=0; j<m; j++){
        int t = 0; int a = 0; int g = 0; int c = 0;
        
        for(int i=0; i<n; i++){
            if(dna[i][j] == 'T') t++;
            else if(dna[i][j] == 'A') a++;
            else if(dna[i][j] == 'G') g++;
            else if(dna[i][j] == 'C') c++;
        }
        
        // 벡터에 문자의 개수를 넣음
        vector<code> v;
        v.push_back(code('T',t));
        v.push_back(code('A',a));
        v.push_back(code('G',g));
        v.push_back(code('C',c));
        
        // 내림차순 정렬
        sort(v.begin(), v.end(), cmp);
        
        // 가장 많이 나온 코드
        ans += v[0].ch;
        
        // 나머지 Hamming Distance
        for(int k=1; k<v.size(); k++){
            cnt += v[k].cnt;
        }
    }
    
    cout << ans << "\n";
    cout << cnt << "\n";
    
    return 0;
}