[백준문제풀이] 1969 DNA

 

풀이일시 : 2020-09-10

​

문제 :

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보다 작거나 같은 자연수이다.

ex)

5 8

TATGATAC

TAAGCTAC

AAAGATCC

TGAGATAC

TAAGATGT

​

 

출력 :

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

ex)

TAAGATAC

7

​

 

풀이 :

그리디알고리즘

해밍거리가 최소화 되는 문자열을 구하는 문제

Hamming Distance는 문자열에서 문자가 다른것의 갯수.

주어진 DNA와 새로운 문자열의 해밍거리를 각각 비교했을때 그 해밍거리의 합이 최소여야한다.

가장 많이 일치해야 된다는 뜻이다.

-> 모든 문자열을 순서대로 읽으면서 가장 많이 등장한 문자들을 결과문자열에 저장하면 될것이다.

 

#include <iostream>
#include <algorithm>
#define MAX 1001

using namespace std;

string a[MAX];
int n, m;//DNA의 개수와 문자열의 길이
string res;
int cnt=0;

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) { //문자열 입력을 다받는다.
		cin >> a[i];  // 다섯개라면 a[0] a[1] a[2] a[3] a[4] 생겼을것 각각에는 8개들어갔을것
	}
	for (int j = 0; j < m; j++) { //문자열 길이만큼 반복한다.
		sort(a, a + n); //A있는게 앞으로 오게정렬
		//이거때문에 헷갈렸었음
		//AGCGA
		//TGAGT 이렇게 있으면 A와 T를 sort 하고 다음번 for문에서는 G와 G 그 다음번에선 C와 A를 sort 한다.
		int i = 0, counts[4] = { 0, };
		while (i < n && a[i][j] == 'A') { //정렬한것에서 A를 다뽑아낸다. j를 두고 i만 늘려나간다.
			counts[0]++; i++;
		}
		while (i<n && a[i][j] == 'C') {
			counts[1]++; i++;
		}
		while ( i < n && a[i][j] == 'G' ) { //while문에 &&로 건것은 앞에꺼가 먼저 걸리고 뒤에조건을 본다.
			counts[2]++; i++;
		}
		while (i < n && a[i][j] == 'T') {
			counts[3]++; i++; //i를 증가시켜 배열이 들어있지 않은곳을 비교하면 에러뜬다.
		}
		int index = 0, min = 2100000000;
		for (int i = 0; i < 4; i++) { //알파벳숫자만큼
			if (min > n - counts[i]) {
				index = i;
				min = n - counts[i]; //그 외에는 다 해밍거리이다.
			}
		}
		if (index == 0)
			res += 'A'; //result문자열에 A를 더해준다.
		if (index == 1)
			res += 'C';
		if (index == 2)
			res += 'G';
		if (index == 3)
			res += 'T';
		cnt += min; //해밍거리들을 더해준다.
		for (i = 0; i < n; i++) {
			a[i][j] = '0';
		}
	}

	cout << res << '\n' << cnt << '\n';
	return 0;
}