[BOJ / C++] #1969 DNA
문제 풀이
Haming Distance를 구할 때는 문자열의 각 위치를 비교해야 하므로
- 입력을 받을 때
cnt[m][4] 배열에, 각 열마다 A,C,G,T가 몇개 들어있는지 넣어준다.
- 0~M-1까지 각 열을 보면서 cnt배열을 이용해 어떤 알파벳이 제일 많은지 구하고, 그 알파벳을 새로운 s의 해당 열의 알파벳으로 지정한다.
이때,(N-제일 많은 알파벳의 개수)
를 Haming Distance에 누적해줘야한다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int main(){
int N,M;
int cnt[50][4]={0,}; // 각 열마다 A,C,G,T 순으로 몇개 들어있는지
cin>>N>>M;
// 입력과 함께, 각 열마다 A,C,G,T가 몇개 들어있는지 세기
for(int i=0;i<N;i++){
string dna;
cin>>dna;
for(int j=0;j<M;j++){
switch(dna[j]){
case 'A':
cnt[j][0]++;
break;
case 'C':
cnt[j][1]++;
break;
case 'G':
cnt[j][2]++;
break;
case 'T':
cnt[j][3]++;
break;
}
}
}
string res="";
int HD=0; //해밍 디스턴스
// 각 열마다.
for(int i=0;i<M;i++){
int max=-1;
int alphaIdx=0;
// 어떤 알파벳이 제일 많은지
for(int j=0;j<4;j++){
if(cnt[i][j]>max){
max=cnt[i][j];
alphaIdx=j;
}
}
HD+=N-max; // N-max만큼 다름.
switch (alphaIdx) {
case 0:
res+="A";
break;
case 1:
res+="C";
break;
case 2:
res+="G";
break;
case 3:
res+="T";
break;
}
}
cout<<res<<"\n"<<HD<<"\n";
}
Author And Source
이 문제에 관하여([BOJ / C++] #1969 DNA), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@inryu/BOJ-C-1969-DNA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)