백준 1969 - DNA, JS

 

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

 

해당 문제를 쉽게 말하면,

주어지는 문자열 중 각 인덱스마다 가장 많은 빈도로 등장하는 알파벳(같은 빈도일 경우 사전순)을 채택하여 문자열을 만들며, (DNA)

문자열을 만들 때마다 (문자열의 갯수 - 채택된 문자열의 빈도 수) 를 누산하여 출력하는 문제다. (Hamming Distance)

 

나는 이를 단순하게 하기 위해, 먼저 배열 안에 객체를 넣어주었다.

이후 이중 반복문에서 들어오는 알파벳과 인덱스에 따라, 해당 인덱스를 가진 객체에 알파벳의 갯수를 추가할 수 있도록 구현했다.

// 이때 M 은 문자열의 길이 = 8
const table = []
// 각 인덱스마다 배열 생성
for(let i = 0 ; i < M ; i ++) table[i] = {}

// 문자열에 접근
data.forEach((str)=> {
  // 문자열 내 알파벳 접근
  str.split('').forEach((el, idx)=> {
  // 단축평가를 활용한 알파벳 갯수 추가
   table[idx][el] =  (table[idx][el] || 0) + 1
  })
})

// table
[
  { T: 4, A: 1 },	// TTATT
  { A: 4, G: 1 },	// AAAGA
  { T: 1, A: 4 },	// TAAAA
  { G: 5 },		// ...
  { A: 4, C: 1 },
  { T: 5 },
  { A: 3, C: 1, G: 1 },
  { C: 4, T: 1 }
]

// 입력 데이터
5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

위 코드에 등장한 단축평가 (table[idx][el] =  (table[idx][el] || 0) + 1)가 궁금하다면? 

2022.12.31 - [개발/JavaScript] - JS - reduce 메서드 / 논리연산자 / 단축평가

 

이후 만들어진 table을 반복문을 통해 가장 많이 등장하는 알파벳 || 사전 순으로 가장 빠른 알파벳을 DNA에 추가하고, Hamming distance를 구해 누산하면 되는데 해당 로직은 다음과 같다.

let result = 0 // hamming distance
let resultStr = '' // DNA
table.forEach((el)=> {
  // 인덱스 별 객체를 정렬 / 등장빈도 순 || 사전 순
  const entries = Object.entries(el).sort((a,b)=> {
    if(a[1] !== b[1]) return b[1] - a[1]
    else return a[0].localeCompare(b[0])
  })
  // 정렬했으므로 entires[0]만 참조
  result += N - entries[0][1] // hamming distance 누산 
  resultStr += entries[0][0] // DNA 추가
})

 

위 코드에 등장한 Object.entires() 메서드가 궁금하다면?

2023.01.29 - [개발/algorithm] - 프로그래머스 - 실패율 / Object.entries()

 

소스 코드

const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
  .toString().trim().split('\n')

const [N,M] = input.shift().split(' ').map(Number)

function solution(data) {
  const table = []
  for(let i = 0 ; i < M ; i ++) table[i] = {}

  data.forEach((str)=> {
    str.split('').forEach((el, idx)=> {
     table[idx][el] =  (table[idx][el] || 0) + 1
    })
  })

  let result = 0
  let resultStr = ''
  table.forEach((el)=> {
    const entries = Object.entries(el).sort((a,b)=> {
      if(a[1] !== b[1]) return b[1] - a[1]
      else return a[0].localeCompare(b[0])
    })
    result += N - entries[0][1]
    resultStr += entries[0][0]
  })

  console.log([resultStr, result].join('\n'))
}

solution(input)