[백준/C++]1969 : DNA

-문제

-풀이

주어진 DNA배열들의 각 자리별 DNA물질의 빈도를 체크한다. 각 자리별 가장 많은 빈도의 물질을 구하고, 이를 자리별로 연결하면 DNA s를 얻어 낼 수 있다.

이때 DNA s를 구성하는데 사용되지 않은 물질은 Hamming distance를 발생한다.

그래서 각 자리별 성분의 빈도수를 확인할때 가장 큰 빈도는 s의 물질로 취하고, 나머지 물질들의 빈도수의 합은 결과적으로 Hamming distance의 총합이 된다.

-코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

using namespace std;

int main(){
    int N, M;
    cin >> N >> M;

    string arry[N];
    for(int i = 0 ; i < N ; i++){
        cin >> arry[i];
    }

    int s[M];//DNA
    int Sum_Hamming=0;
    int max=0, max_index=0;
    vector<int>count(4);//ATGC -> ABC순으로 변경

    for(int i = 0 ; i < M ; i++){//find DNA 's' //주어진 DNA의 자리수마다 빈도를 검사한다
        count = {0,0,0,0};//자리별로 빈도수를 체크하고 초기화되는 임시 저장소를 만든다.
        for(int j = 0 ; j < N ; j++){
            if     (arry[j][i]=='A')count[0]++;
            else if(arry[j][i]=='C')count[1]++;
            else if(arry[j][i]=='G')count[2]++;
            else if(arry[j][i]=='T')count[3]++;
        }

        for(int a = 0 ; a < 4 ; a++){//가장 많은 빈도는 s의 i번째에 저장한다.이때 알파벳은 인덱스 숫자로 저장한다
            if(max < count[a]) {
                max_index = a;
                max = count[a];
            }
        }
        s[i] = max_index;
        max_index=0;
        max = 0;
        
        Sum_Hamming += ( accumulate(count.begin(), count.end(), 0) - *max_element(count.begin(),count.end()) );
        //빈도를 체크할때 가장 많은 빈도를 제외한 알파벳의 빈도수는 모두 Hamming에 더한다.
        //이 코드는 count에 있는 모든 수를 더한 후 가장 큰 빈도수를 빼는 계산이다. 이로써 이 자리의 Hamming_distance를 얻는다.
    }


    for(int i = 0 ; i < M ; i++){
        if     (s[i]==0)cout<< "A";
        else if(s[i]==1)cout<< "C";
        else if(s[i]==2)cout<< "G";
        else if(s[i]==3)cout<< "T";
    }
    cout << '\n' << Sum_Hamming << endl;

    return 0;

}

-참고

s[i] = max_element(count.begin(),count.end())-count.begin();

위 코드로 count의 가장 큰 값의 인덱스를 저장할 경우 빈도수가 같을때 알파벳 순을 적용할 수 없었다. 따라서 아래와 같이 count의 인덱스를 알파벳 순으로 변경하고 for문을 이용해서 인덱스가 빠른 경우가 저장되도록 하였다.

        for(int a = 0 ; a < 4 ; a++){
            if(max < count[a]) {
                max_index = a;
                max = count[a];
            }
        }
        s[i] = max_index;
        max_index=0;
        max = 0;