백준(BOJ) 1969번 DNA

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

입력

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

출력

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

나의풀이 :

전체 문자들을 세로로 비교해가면서 가장 높은 숫자들을 선택해준후 벡터에 넣는다.

 숫자는 골라졌지만 가장 높은 숫자는 아닌 혹은 사전순으로 우선 순위가 아래인 숫자들의 수를 subsum을 통해 세어준다.

코드 ( C ++ )

#include <iostream>

#include <vector>

#include <string>

using namespace std;

int N, M;

string dna[1001];

vector<char> ans;

int sum = 0;

int main()

{

cin >> N >> M;

for (int i = 0; i < N; ++i)

{

cin >> dna[i];

}

for (int i = 0; i < M; ++i) {

int check[26]{ 0 };  // 알파벳 체크용 26개 짜리 배열을 만든다

for (int j = 0; j < N; ++j)

{

check[dna[j][i] - 65] += 1; // 세로로 알파벳을 세면서 체크배열에 +1 해준다.

}

int max = 0, maxindex = 0;

for (int i = 0; i < 26; ++i)  // 26번 a부터 돌면서 최고값, 그때의 index를 구한다.

{

if (max < check[i]) {

max = check[i];

maxindex = i;

}

}

int subsum = 0;

 // 한번이상 표기 됬으나 최대값의 index는 아닌 알파벳들을 세준다. 

for (int i = 0; i < 26; ++i) {

if (check[i] > 0 && check[i] <= max && i != maxindex) 

subsum += check[i];

}

ans.push_back(maxindex + 65); //최대값 알파벳을 넣어준다.

sum += subsum; 

}

for (int i = 0; i < ans.size(); ++i)

cout << ans[i];

cout << endl;

cout << sum << endl;

return 0;

}