본문 바로가기

백준1337 - 올바른 배열 JS 본문

개발/algorithm

백준1337 - 올바른 배열 JS

자전하는명왕성 2023. 10. 12. 09:24
반응형

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)
반응형
Comments