5주차(그리디) - [C++]백준1969 DNA

01 Apr 2022 in Study on Algorithm

백준1969 DNA 링크

문제

예제 입력

---

코드

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); //cin 실행속도 향상

	string s = "";
	int count = 0;
	map<char, int> nucleotide = { { 'A', 0 },{ 'C', 0 },{ 'G', 0 }, { 'T', 0 } };

	int n, m;
	cin >> n >> m;
	vector<string> dna;
	for (int i = 0; i < n; i++) {
		string tmp;
		cin >> tmp;
		dna.push_back(tmp);
	}

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			nucleotide[dna[j][i]]++;
		}

		int max = 0;
		char max_char = ' ';
		for (auto& tmp : nucleotide) {
			if (tmp.second > max) {
				max = tmp.second;
				max_char = tmp.first;
			}
			tmp.second = 0;
		}
		count += n - max;
		s += max_char;
	}
	cout << s << "\n" << count << "\n";
}

설명

이 문제는 일정 길이의 DNA들과 HD(Hamming Distance)가 최소인 새로운 DNA를 생성하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector와 map을 사용하여 구현했습니다. 일정 길이의 여러 DNA를 입력 받아 각각의 DNA의 첫 번째 유전물질의 분자를 비교하여 어느 것이 제일 많이 있는 파악하고 그 분자로 생성해야 HD가 최소가 됩니다. 그렇게 각각의 분자마다 선택하여 생성합니다.

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

<map>
-map<자료형, 자료형> 변수명; :  Key-val형태 자료구조 사용(사전순으로 자동저장)

---

결과