[백준] 1969 DNA Node.js (Greedy)

Janet·2023년 6월 23일
0

Algorithm

목록 보기
229/314

문제

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가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

예제 입력 1

5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

예제 출력 1

TAAGATAC
7

예제 입력 2

4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA

예제 출력 2

ACGTACGTAA
6

예제 입력 3

6 10
ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA

예제 출력 3

AAGTTACCAA
12

문제풀이

💡 문제풀이 과정

  • 주어진 입력값에서 각각의 문자열 인덱스마다 나온 문자의 개수를 카운트 해야하므로 중첩 반복문을 적절하게 사용하는 것이 중요했다.
  • 사용된 문자열의 개수가 같은 경우 알파벳순으로 앞서는 것을 출력해야 하므로 4가지 뉴클레오티드를 ‘A’부터 배열에 담아준다. const char = ['A', 'C', 'G', 'T'];
  • 문자 개수를 카운트할 카운트 변수 또한 길이가 4인 배열의 형태로 선언하여 최다 카운트된 문자열의 인덱스를 반영한다. let cnt = [0, 0, 0, 0];

✅ 답안

const filePath = process.platform == 'linux' ? '/dev/stdin' : './input.txt';
const [nums, ...DNAs] = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = nums.split(' ').map(Number);
const char = ['A', 'C', 'G', 'T'];
let answer = '';
let sumDist = 0;

for (let i = 0; i < M; i++) {
  let cnt = [0, 0, 0, 0];
  for (const dna of DNAs) {
    for (let j = 0; j < char.length; j++) {
      if (dna[i] === char[j]) cnt[j]++;
    }
  }
  const maxCnt = Math.max(...cnt);
  answer += char[cnt.indexOf(maxCnt)];
  sumDist += N - maxCnt;
}

console.log(answer);
console.log(sumDist);
profile
😸

0개의 댓글