[알고리즘/백준/6187] DNA(Nodejs, 완전탐색)

문제

---

https://www.acmicpc.net/problem/1969

1969번: DNA

 

풀이

---

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [n, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, M] = n.split(" ").map(Number);
const DNAs = arr.map((row) => row.split(""));

const nucle = ["A", "C", "G", "T"]; // 사전 순
let answer = "";
let distance = 0;

// M번째 위치에서 가장 많이 사용된 알파벳을 M번째 위치에 넣기
for (let i = 0; i < M; i++) {
  const cntArr = Array.from({ length: 4 }).fill(0);
  for (let j = 0; j < N; j++) {
    cntArr[nucle.indexOf(DNAs[j][i])] += 1;
  }

  // 가장 많은 알파벳 M번째 위치에 넣기
  const maxVal = Math.max(...cntArr);
  const idx = cntArr.indexOf(maxVal);
  answer += nucle[idx];
  // hamming distance 더하기
  distance += N - maxVal;
}

console.log([answer, distance].join("\n"));

 

 

---

 

Hamming distance의 합이 가장 작은 DNA s를 구하는 문제이다. s와 주어진 입력에 있는 DNA 각각과의 hamming distance를 구해 모두 더했을 때 그 값이 가장 작아야 한다.

 

Hamming distance는 DNA 간 같은 위치의 뉴클레오티드 문자가 다른 것의 개수이다. 따라서 각 위치에서 가장 많이 사용된 문자를 구한다. 해당 문자를 M번째 위치에 가지고 있으면 hamming distance는 최소가 된다. 

 

여기서 주의해야 할 점은 그러한 DNA가 여러 개 있을 때에는 사전 순으로 가장 앞서는 것을 구해야 한다는 것이다. 이를 위해 가능한 문자를 nucle이라는 배열에 사전 순으로 저장하고, cntArr에도 해당 문자 순서로 M번째에서 사용된 횟수를 각각 구한다. 후에 어떤 문자를 answer의 M번째 위치에 추가할지를 결정할 때 idx는 최대 사용 횟수(Math.max(...cntArr))의 인덱스를 indexOf를 이용해 가장 처음에 나오는 값(사전 순 앞서는 것)을 반환한다.

 

5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

 

그렇다면 hamming distance는 어떻게 구하면 될까? answer의 M번 째 위치에 해당하는 문자가 정해졌으니 해당 문자를 제외한 다른 문자들의 개수를 세면 된다. 

 

예를 들어 answer = "T"라면 첫 번째 위치에서 T가 아닌 문자는 A 하나로 1이 된다. answer = "TAAGATA"까지 구했다면 일곱 번째 위치에서 A가 아닌 문자는 C, G가 각각 하나씩 사용되어 2가 된다. 이처럼 입력 전체 S ~ Sn의 개수인 N 가운데 최대로 사용된 문자와 다른 문자의 개수를 구하면 된다. 이것은 N에서 사용 횟수의 최댓값을 빼준 값이다.