1969_DNA

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

1969번: DNA

문제

  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개의 길이가 같은 DNA가 주어져 있을 때(이 DNA를 a1a2a3a4...이라고 하자) Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 a1의 Hamming Distance + s와 a2의 Hamming Distance + s와 a3의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.

입력

  첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.

출력

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

예제 입력 1 복사

5 8

TATGATAC

TAAGCTAC

AAAGATCC

TGAGATAC

TAAGATGT

예제 출력 1 복사

TAAGATAC

7

예제 입력 2 복사

4 10

ACGTACGTAC

CCGTACGTAG

GCGTACGTAT

TCGTACGTAA

예제 출력 2 복사

ACGTACGTAA

6

---

문제 접근

  내가 생각한 문제 해결 방법은 예를 들어 DNA배열에 있어서 첫번째 알파벳이 A의 비율이 많다면 A로 하는 식의 방법이다. 만일 다 겹치지 않는다면 첫번째 알파벳으로 한다. 문제는 알파벳을 어떻게 카운트해서 최고로 많이 나온 알파벳이 뭔지를 파악하는 것이다.

 

  가장 간단하게 생각하는 방법은 알파벳의 총 숫자와 똑같은 배열을 만드는 것이다. 그리고 아스키코드를 변환시켜 그것을 idx로 삼아 누적해 나가는 것이다. 그렇게 하면 총 26번안에 가장 큰 알파벳이 뭔지 찾을 수 있을 것이다.

 

/* DNA */
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, cnt = 0;
int alpha[26];
vector<string> order;
string ans = "";

int main(void) {
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		string temp;
		cin >> temp;
		order.push_back(temp);
	}
	
	for(int i = 0; i < m; i++) {
		int max = 0, idx;
		fill(alpha, alpha + 26, 0);
		// i번째 알파벳들의 나온 비율을 배열에 누적
		for(int j = 0; j < n; j++) {
			alpha[order[j][i] - 65] += 1;
		}
		// i번째에서 가장 많이 나온 알파벳을 찾는다.
		for(int j = 0; j < 26; j++) {
			if(max < alpha[j]) {
				idx = j;
				max = alpha[j];
			}
		}
		ans += char(idx + 65);
	}
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(order[i][j] != ans[j]) {
				cnt += 1;
			}
		}
	}
	cout << ans << '\n' << cnt << '\n';
	return 0;
}

문제를 자세히 보니 알파벳은 4개밖에 사용안하므로 자잘한 속도향상을 할 수도 있을 거 같다.