[백준] 1969번 DNA

[문제]

Hamming Distance(이하 HD)란 길이가 같은 두 DNA가 있을 때, 각 위치의 문자가 다른 것의 개수입니다. 

예로, AGCAT와 GGAAT의 HD는 0, 3번째가 다르므로 2입니다.

DNA들이 주어져 있을 때 HD의 합이 가장 작은 새로운 DNA s를, 그리고 이 s는 사전순서로 가장 앞에 오는 것 구하기! 

DNA가 a, b, c, d 이렇게 4개 주어졌다 하면, s와 a의 HD, s와 b의 HD, ... , s와 d의 HD 를 합한게 최소가 되는 s를 구하라는 의미입니다.

 

[풀이]

생각보다 단순하게 Greedy하게 풀 수 있는 문제입니다.

문제상의 예시를 바탕으로 보면

TATGATAC

TAAGCTAC

AAAGATCC

TGAGATAC

TAAGATGT

 

우선 0번째 index를 보면 T가 4개로 제일 많으니 s에 T를 추가해줍니다. 

그런식으로 7번째 index까지 진행하면 답을 도출할 수 있는 간단한 문제입니다. 

주의할 것은 만약 A가 2개 T도 2개라 하면 사전순이기에 A를 추가해 줘야 합니다.

저는 알파벳 ascii code를 활용해서 했습니다

사실 문자는 4종류뿐인데 26개의 알파벳 배열을 사용하다보니 메모리 측면에서 비효율적이긴 하지만

문제 해결에 있어서 큰 차이는 아니다보니 편의상 그렇게 진행하였습니다.

 

아래는 해당 코드 입니다!

#include <iostream>
#include <string>
using namespace std;
int main(void) {
	int n, m;
	cin >> n >> m;
	string dna[1000];
	int alphabet[26];
	string s = "";
	int cnt = 0;
	for (int i = 0; i < n; i++) cin >> dna[i];
	for (int i = 0; i < m; i++) {
		int max = 0;
		fill_n(alphabet, 26, 0);
		// 알파벳 중복되는 개수 구하기
		for (int j = 0; j < n; j++) {
			int idx = dna[j][i] - 65;
			alphabet[idx]++;
			if (max < alphabet[idx]) max = alphabet[idx];
		}
		// 알파벳 중 중복되는 개수가 제일 많으면서 
		// 사전상 제일 앞에 오는 문자 찾기
		for (int j = 0; j < 26; j++) {
			if (alphabet[j] == max) {
				s += (char)(j + 65);
				break;
			}
		}
		// DNA의 i번째 문자들 중 s의 i번째 문자와 다른 것들의 수 ++
		for (int j = 0; j < n; j++)
			if (s[i] != dna[j][i]) cnt++;
	}
	cout << s << '\n' << cnt;
	return 0;
}

 

질문이나 지적사항은 댓글 부탁드립니다 :)