DNA (백준 - 1969번)

우선 Hamming Distance의 합이 가장 작은 DNA부터 구해야 한다.

 

입력받은 DNA들에서 각 번째마다 가장 많이 존재하는 뉴클레오티드를 종합하여 조합하면 Hamming Distance의 합이 가장 작은 DNA를 찾을 수 있다. 

 

TATGATAC

TAAGCTAC

AAAGATCC

TGAGATAC

TAAGATGT

 

이 DNA를 예로 들어보자. 첫번째에 가장 많이 존재하는 뉴클레이오티드는 T이다. 두번째는 A, 세번째는 A, 네번째는 G, 다섯번째는 A, .... 이렇게 해서 우리가 찾는 DNA의 값은 TAAGATAC가 된다.

 

하지만 이 DNA가 여러개 존재 할 수 있다는 것에 주목하자. 각 번째에서 즉 존재하는 뉴클레오티드 횟수가 서로 동일할 수 있다는 것이다. 이 경우에는 사전 순으로 했을때 가장 처음에 오는 DNA를 찾아야 한다.

 

ACGTACGTAC

CCGTACGTAG

GCGTACGTAT

TCGTACGTAA

 

다음 경우를 살펴보자. 첫번째의 뉴클레이오티드는 서로 하나씩 존재한다. 이 경우 A, C, G, T 모두 존재하는 뉴클레오티드 횟수가 서로 동일하다. 사전 순으로 가장 처음에 오는 DNA를 찾아야 하므로 첫번째는 A가 될것이다. 이렇게 하면 찾는 DNA의 값은 ACGTACGTAA가 된다. 

 

구한 DNA를 바탕으로 입력받은 모든 DNA와 비교하여 서로 동일한 뉴클레이오티드가 아닌 경우 카운트를 하나씩 증가시켜주면 답을 도출해낼 수 있다.

 

코드는 다음과 같다.

#include <iostream>
using namespace std;

enum INFO
{
	A,C,G,T, INFO_END
};

int main()
{
	char dna[1000][50] = { 0, };
	int info[50][INFO_END] = { 0, };
	char resultDna[50] = { 0, };
	int resultCount = 0;

	int dnaCount, materialCount;
	cin >> dnaCount >> materialCount;

	for (int i = 0; i < dnaCount; ++i)
	{
		cin >> dna[i];
	}

	for (int i = 0; i < dnaCount; ++i)
	{
		for (int j = 0; j < materialCount; ++j)
		{
			switch (dna[i][j])
			{
			case 'A': ++info[j][A]; break;
			case 'C': ++info[j][C]; break;
			case 'G': ++info[j][G]; break;
			case 'T': ++info[j][T]; break;
			}
		}
	}

	for (int i = 0; i < materialCount; ++i)
	{
		char infoDNA = 0;
		int max = 0;
		for (int j = 0; j < INFO_END; ++j)
		{
			if (max < info[i][j])
			{
				switch (j)
				{
				case A: infoDNA = 'A'; break;
				case C: infoDNA = 'C'; break;
				case G: infoDNA = 'G'; break;
				case T: infoDNA = 'T'; break;
				}
				max = info[i][j];
			}
		}
		resultDna[i] = infoDNA;
	}

	for (int i = 0; i < dnaCount; ++i)
	{
		for (int j = 0; j < materialCount; ++j)
		{
			if (resultDna[j] != dna[i][j])
				++resultCount;
		}
	}

	cout << resultDna << endl;
	cout << resultCount << endl;
}