백준 1969번: DNA

[문제 링크]

1969번: DNA

---

간단한 그리디 알고리즘 문제였다.

각 자리마다 가장 많이 등장하는 알파벳을 뽑아서 문자열을 만들어주면 Hamming Distance의 합을 가장 작게 만들 수 있다.

 

사전순으로 가장 앞서는 것을 출력해야 하기 때문에 뉴클레오티드 A, T, G, C 를 A, C, G, T 순으로 비교하였다.

---

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

const int INF = 987654321;
char nuc[4] = { 'A', 'C', 'G', 'T' };
string DNA[1000];

int max(int a, int b) { return a > b ? a : b; }

string Greedy(int N, int M)
{
	string s;

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

		for (int j = 0; j < 4; j++)
		{
			int cnt = 0;
			for (int k = 0; k < N; k++)
				if (nuc[j] == DNA[k][i])
					cnt++;

			if (idxCnt < cnt)
			{
				idxCnt = cnt;
				idxChar = nuc[j];
			}
		}

		s.push_back(idxChar);
	}

	return s;
}

int main(void)
{
	int N, M;
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		cin >> DNA[i];

	string res = Greedy(N, M);

	int hamming = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (res[j] != DNA[i][j])
				hamming++;

	cout << res << endl;
	cout << hamming << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 122 day