BOJ 1969 DNA

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

1969번: DNA

 

이 문제는 brute force 문제이다

 

DNA 염기 { A, C, G, T } 로 구성된 문자열이 N개 주어졌을 때, 각 자리수의 가장 빈도수가 많은 문자만 뽑으면 된다

 

문제에서는 Hamming distance 등 생소한 용어로 혼란을 주지만 문제 자체만 보면 각 자리수의 빈도수가 가장 높은 문자만

 

뽑으면 그것이 전체 DNA sequence 중 가장 차이가 적은 문자열이 된다

 

counting을 위해서 map 자료구조를 이용했고, 사전 순을 맞추기 위해 max 를 검사할 때 사전 순으로 검사하도록 한다

 

 

 

소스코드

 

#include<stdio.h>
#include<vector>
#include<string>
#include<map>
using namespace std;
int n,m;
char buf[55];
char order[4] = { 'A', 'C', 'G', 'T'};
 
int main(){
  scanf("%d %d",&n,&m);
  vector<string> v;
  for(int i=0;i<n;i++){
    scanf(" %s", buf);
    v.push_back(string(buf));
  }
  vector< pair<char, int> > ans;
  for(int i=0; i<m; i++){
    map<char, int> c;
    for(int o=0; o<4; o++)
      c[order[o]] = 0;    
    for(int j=0; j<n; j++){
      c[v[j][i]] += 1;
    }
    int max_ = 0, diff = 0;
    char d;
    for(int o=0; o<4; o++){
      diff += c[order[o]];
      if(max_ < c[order[o]]){
        max_ = c[order[o]];
        d = order[o];
      }
    }
    ans.push_back(make_pair(d, diff-max_));
  }
  int cnt = 0;
  for(int i=0;i<ans.size();i++){
    printf("%c", ans[i].first);
    cnt += ans[i].second;
  }
  printf("\n%d\n", cnt);
  return 0;
}