[1969번] DNA

www.acmicpc.net/problem/1969

1969번: DNA

풀이

문제의 예제 2로 살펴보겠습니다.

[입력]

4 10

ACGTACGTAC

CCGTACGTAG

GCGTACGTAT

TCGTACGTAA

 

주어진 입력을 배열로 저장한 후 각 행의 같은 열에 있는 문자의 개수를 비교하고 개수를 저장합니다.

1열: A C G T -> A: 1개 / C: 1개 / G: 1개 / T: 1개

2열: C C C C -> A: 0개 / C: 4개 / G: 0개 / T: 0개

3열: G G G G -> A: 0개 / C: 0개 / G: 4개 / T: 0개

....

 

문자 개수의 비교를 통하여 각 열마다 가장 많이 포함되어 있는 문자를 string으로 저장합니다. 이때 문자의 개수가 동일하다면 먼저 나오는 문자를 저장합니다.

문자의 개수를 저장해 두었기 때문에 (n-문자 개수)를 cnt에 반복해서 더해주어 Hamming Distance를 계산할 수 있습니다.

 

반복문을 통해 m열까지 모두 비교하여 문제를 해결할 수 있습니다.

전체 코드

#include <iostream>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;

	char arr[1000][50];
	int dna[4] = { 0, }; // [0]: A, [1]: C, [2]: G, [3]: T
	string s = "";
	int cnt = 0;

	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 0;i < m;i++) {
		for (int j = 0;j < n;j++) {
			if (arr[j][i] == 'A') dna[0]++;
			if (arr[j][i] == 'C') dna[1]++;
			if (arr[j][i] == 'G') dna[2]++;
			if (arr[j][i] == 'T') dna[3]++;
		}
		int max = -1;
		int tmp;
		for (int j = 0;j < 4;j++) {
			if (dna[j] > max) {
				max = dna[j];
				tmp = j;
			}
			dna[j] = 0;
		}
		if (tmp == 0) {
			s += 'A';
		}
		else if (tmp == 1) {
			s += 'C';
		}
		else if (tmp == 2) {
			s += 'G';
		}
		else if (tmp == 3) {
			s += 'T';
		}
		cnt += (n - max);
	}

	for (auto x : s) {
		cout << x;
	}
	cout << endl << cnt << endl;
}