[백준_1969] DNA ( 그리디 - 자바스크립트 )

문제

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

1969번: DNA

 

How to Solve ?

 

 

미션 1 -  가장 Hamming Count가 낮은 문자열은 찾기

 

모든 문자열과 비교 했을 때, 가장 차이가 적은 문자열을 찾는 방법 중 가장 먼저 떠오른 방법은

 

[1] 이중 포문으로 모든 문자열과 대조한다. 

 

=> 아무리 생각해도 너무 비효율적이고 탐색하는 문자열까지 합하면 3중 포문이였기에 바로 버렸다

 

 

 

 [2] 자리 별로 가장 많이 사용된 문자열을 합친다 

 

아래의 그림처럼 각 자리별로, 가장 많이 사용되는 문자열을 합치면 최소 "해밍 카운트"를 가진 문자열을 구할 수 있다.

 

 

 

미션 2 -  다른 개수 세기

 

이건 미리 만들어 놓은 문자열을 가지고 비교만 하면 결과를 얻을 수 있다 :)

 

코드

function solve() {
  let intersection = "";
  let count = 0;

  for (let i = 0; i < M; i++) {
    const alphabet = Array(26).fill(0);

    for (let j = 0; j < N; j++) {
      alphabet[DNA[j][i].charCodeAt(0) - 65] += 1;
    }

    intersection += String.fromCharCode(
      alphabet.indexOf(Math.max(...alphabet)) + 65
    );
  }

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (DNA[i][j] != intersection[j]) {
        count += 1;
      }
    }
  }

  console.log(intersection);
  console.log(count);
}

const [N, M] = [5, 8];
const DNA = ["TATGATAC", "TAAGCTAC", "AAAGATCC", "TGAGATAC", "TAAGATGT"];
solve();

// 출제자의 의도에 대해서 고민해보자