알고리즘(C++) / 백준 1969 : DNA

1969

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

 

출력

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

 

코드

//1969 DNA
#include <iostream>
#include <algorithm>
#include <vector>
#include <vector>
char DNA[1000][50];  //뉴클레오티드 쌍
using namespace std;

bool compare(const pair<int, int>& a, const pair<int, int>& b) {
	//첫 번째 수가 같다면
	if (a.first == b.first)
		return a.second < b.second; //두 번째 수로 오름차순
	return a.first > b.first; //첫 번째 수가 더 작은 수가 앞으로 내림차순
}

int main() {
	int N, M;
	char s[50];
	int sum = 0;
	vector <pair<int, char>> dna; //뉴클레오티드 하나
	
	cin >> N >> M;

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

	int check_dna = 0; 
	for (int i = 0; i < M; i++) {
		dna.clear();
		for (int j = 0; j < N; j++) {
			check_dna = 0;
			for (int k = 0; k < dna.size(); k++) {
				if (dna[k].second == DNA[j][i]) {
					dna[k].first++; //size 증가
					check_dna = 1;
					break;
				}
			}
			if (check_dna == 0) {
				dna.push_back(make_pair(1, DNA[j][i])); // dna를 하나 생성하여 저장
			}
		}

		if (dna.size() == 1) {
			s[i] = dna[0].second; // 한종류의 dna만 존재할 때
			continue;
		}

		sort(dna.begin(), dna.end(), compare); //내림차순으로 정렬

		s[i] = dna[0].second;
		sum += (N - dna[0].first);
	}

	for (int i = 0; i < M; i++) {
		cout << s[i];
	}

	cout << endl << sum << endl;

	return 0;
}

 

설명

DNA을 2차 배열로 선언하고 N과 M을 입력받아 여러개의 DNA를 저장할 수 있다.

 

입력받은 여러 개의 DNA의 각 자리를 보고 그 자리에서 가장 많은 dna를 선택하여 s에 저장한다.

각 자리에서 가장 많은 dna의 수를 빼서 hamming distance를 구할 수 있다.

 

dna 벡터에 각 자리의 dna의 수를 저장한다. 그중 가장 개수가 많은 dna와 개수가 똑같다면 사전 순으로 가장 앞서는 것을 s에 자리에 맞게 저장한다. 

 

가장 많은 dna와 사전 순으로 가장 앞서는 것을 찾기 위해 내림차순으로 정렬하고 값이 똑같다면 dna는 사전 순으로 정렬한다. 다음과 같이 정렬하기 위해 compare 함수를 다음과  작성하였다. 

 

결과

 

고찰

문제를 풀면서 sort하는 부분에서 막혔다.

greater<int>() 을 사용하여 내림차순으로 정렬하였다. 하지만 다음과 같이 정렬하면 내림차순으로 정렬되지만 first(size)가 같다면 second도 내림차순으로 정렬된다. 하지만 second(dna)는 사전 순으로 정렬되어야 하므로 오름차순으로 정렬되어야 한다. 그래서 compare함수를 직접 만들어 first는 내림차순으로 second는 오름차순으로 정렬하도록 하는 함수를 작성할 수 있었다. 

 

난이도

●●◐○○