취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1969번 문제인 DNA이다.
문제는 아래 링크를 확인하자.

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

해밍 거리(Hamming Distance)는 길이가 같은 두 문자열에 대하여 순서대로 각 문자를 대응시킬 때, 서로 다른 문자가 대응된 개수를 의미한다. 이는 가장 간단한 편집거리(Edit Distance) 중 하나이기도 하다.

주어지는 문자열들의 각 i번째 문자는 다른 순서의 문자와 대응될 일이 없으므로, 각 순서에 대하여 가장 많이 등장한 문자를 새로 만드는 문자열의 문자로 선택하는 것이 항상 최선임을 알 수 있다. 그러한 문자가 여럿 있을 경우, 사전순으로 가장 빠른 문자열을 만들어야하므로 A, C, G, T 순으로 고르도록 하자.

아래는 제출한 소스코드이다.

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

int cnt[50][4];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M; cin >> N >> M;
	for (int n = 0; n < N; n++) {
		string s; cin >> s;
		for (int i = 0; i < M; i++) {
			if (s[i] == 'A') cnt[i][0]++;
			else if (s[i] == 'C') cnt[i][1]++;
			else if (s[i] == 'G') cnt[i][2]++;
			else cnt[i][3]++;
		}
	}

	int dist = 0;
	for (int i = 0; i < M; i++) {
		int x = (cnt[i][0] >= cnt[i][1]) ? 0 : 1;
		int y = (cnt[i][2] >= cnt[i][3]) ? 2 : 3;
		int idx = (cnt[i][x] >= cnt[i][y]) ? x : y;

		dist += cnt[i][idx];

		if (idx == 0) cout << 'A';
		else if (idx == 1) cout << 'C';
		else if (idx == 2) cout << 'G';
		else cout << 'T';
	}
	cout << '\n' << N * M - dist;
}