백준 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)
반응형
'개발 > algorithm' 카테고리의 다른 글
프로그래머스 - Lv.3 가장 먼 노드 (BFS) JS (0) | 2023.09.09 |
---|---|
백준 2910 - 빈도정렬 JS (0) | 2023.09.08 |
백준 11725 - 트리의 부모찾기 (BFS) JS (0) | 2023.09.06 |
백준 1759 - 암호 만들기 (백트래킹) JS (0) | 2023.09.05 |
프로그래머스 - Lv.2 삼각달팽이 JS (0) | 2023.09.04 |
Comments