백준 1969 DNA c++ (완전탐색)

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

1969번: DNA

문제

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개의 길이 M인 DNA s1, s2, ..., sn가 주어져 있을 때 Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 s1의 Hamming Distance + s와 s2의 Hamming Distance + s와 s3의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.

입력

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

출력

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

알고리즘 분류

• 문자열
• 브루트포스 알고리즘

풀이

입력된 모든 문자열의 각 자릿수마다, 가장 많이 나오는 문자를 찾고, 문자열의 갯수에서 가장 많이 나온 문자의 갯수를 빼면, 각 자릿수에 들어와야 할 문자와, Hamming Distance를 구할 수 있다.

각 자릿수에 가장 많이 나오는 문자를 찾는 것은, map을 이용해서 사전 순으로 저장하였다.

이 중 앞에서부터 가장 많이 나온 문자를 찾으면 된다.

시간 복잡도는 총 O(m*n^2)인데 m=50 n=1000이므로 완전 탐색으로 풀 수 있다. 

 

코드

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	//n<1000
	//m<=50
	

	string input[1000];
	int sum = 0;
	string ans = "";
	for (int i = 0; i < n; i++) {
		cin >> input[i];
	}
	for (int i = 0; i < m; i++) {
		map<char, int> ma;
		for (int j = 0; j < n; j++) {
			ma[input[j][i]]++;
		}
		char ch;
		int max=0;
		for (auto o : ma) {
			if (max < o.second) {
				max = o.second;
				ch = o.first;
			}
		}
		ans += ch;
		sum += n-max;
	}
	cout << ans << '\n' << sum;
	return 0;
}