백준1337 - 올바른 배열 JS 본문
반응형
https://www.acmicpc.net/problem/1337
문제는 길이가 n인 배열을 주고, 길이가 5이며 인접한 수의 차이가 1인 연속적인 배열을 만든다고 할 때,
추가해야 할 최소 원소의 갯수를 출력하는 문제다.
각 원소를 해쉬 테이블에 저장해둔 뒤, 검색하는 용도로 활용했다.
const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
.toString().trim().split('\n')
function solution(data) {
data.shift()
const table = {}
data.forEach(el => table[el] = true)
let max = 0
data.forEach((el)=> {
// el이 최솟값이며 가진 원소들로 인접한 배열을 만든다고 할 때
// cnt는 el과 el + 1 ~ el + 4 사이의 원소의 갯수를 기록
// table[el]은 무조건 존재하므로 굳이 셀 필요없음
let cnt = 0
for(let j = 1 ; j < 5 ; j ++) {
table[+el + j] && cnt ++
}
max = cnt > max ? cnt : max
})
// max의 최댓값은 4이며, 이는 '구성할 수 있는 원소의 수'를 의미
// 따라서 필요한 원소의 갯수를 구하기 위해 4 - max
console.log(4-max)
}
solution(input)
반응형
'개발 > algorithm' 카테고리의 다른 글
백준2644 - 촌수계산 (BFS) JS (0) | 2023.10.15 |
---|---|
백준11048 - 이동하기 (DP) JS (0) | 2023.10.14 |
백준17175 - 피보나치는 지겨웡~ (DP) JS (0) | 2023.10.10 |
백준13909 - 창문 닫기 JS (0) | 2023.10.09 |
프로그래머스 - Lv.2 2개 이하로 다른 비트 JS (1) | 2023.10.08 |
Comments