DNA

문제

백준 1969번 - DNA

언어

JavaScript

순서도

주어진 DNA 들의 각 자리별로 각 문자의 개수를 세고, 가장 개수가 많은 문자로 그 자리를 결정
만약, 개수가 동일하다면 사전 순으로 먼저 오는 문자로 그 자리를 결정
그와 동시에 Hamming Distance 구하기
모든 자리에 대해서 위의 1, 2, 3 번 과정을 수행 후 만들어진 문자열을 출력

문제 풀이 step 1

DNA 는 서로 다른 4 가지의 뉴클레오티드로 이루어져 있습니다. (Adenine, Thymine, Guanine, Cytosine)
우리는 어떤 DNA 를 표현할 때, 이 DNA 를 이루는 뉴클레오티드의 첫 글자를 따서 표현합니다. (TAACTGCCGAT)
그리고 Hamming Distance 란 길이가 같은 두 DNA 가 있을 때, 각 위치의 뉴클레오티드 문자가 다른 것의 개수입니다.
- 만약에 “AGCAT” 와 “GGAATT” 는 첫 번째 글자와 세 번째 글자가 다르므로 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) + … 의 합이 최소가 되는 경우의 s 를 구하는 것입니다.

문제 풀이 step 2

주어진 DNA 들에 대해서 각 자리별로 각 문자의 개수를 셉니다.
그 중에서 가장 개수가 많은 문자로 그 자리를 결정합니다.
만약, 개수가 동일하다면 사전 순으로 먼저 오는 문자로 그 자리를 결정합니다.
그리고 그 자리에 결정된 문자와 다른 문자의 개수인 Hamming Distance 를 갱신합니다.
위의 과정을 모두 수행하면, Hamming Distance 의 합이 가장 작은 DNA s 가 나오게 되고, Hamming Distance 의 총합을 구할 수 있게 됩니다.
추가 설명은 주석으로 작성하겠습니다.

후기

영화 GATTACA 가 생각나서, 재미있게 풀 수 있었던 문제입니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);

	let dna = "";
	let hammingDistance = 0;

	const arr = input.slice(1);
	for (let i = 0; i < m; i++) {
		let cnts = [
			["A", 0],
			["C", 0],
			["G", 0],
			["T", 0],
		];

		// 각 자리 별로 각 문자의 개수가 몇 개인지 세기
		for (let j = 0; j < n; j++) {
			if (arr[j][i] === "A") cnts[0][1] += 1;
			else if (arr[j][i] === "C") cnts[1][1] += 1;
			else if (arr[j][i] === "G") cnts[2][1] += 1;
			else cnts[3][1] += 1;
		}

		// 가장 많이 겹치는 문자 순으로 정렬하고, 만약 겹치는 개수가 동일하다면 사전순으로 정렬
		cnts.sort((a, b) => {
			const [ch1, cnt1] = a;
			const [ch2, cnt2] = b;

			if (cnt1 === cnt2) {
				if (ch1 < ch2) return -1;
				return 1;
			}
			return cnt2 - cnt1;
		});

		// 가장 많이 겹치며 사전순으로 앞서는 문자로 그 자리를 결정
		dna += cnts[0][0];

		// Hamming Distance 값 갱신
		hammingDistance += n - cnts[0][1];
	}

	return dna + "\n" + hammingDistance;
};

console.log(solution(input));