백준5671 - 호텔 방 번호 (DP) JS

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

 

문제는 범위가 주어질 때, '중복되어 사용되지 않는 수'가 몇 개인지 구하는 문제다.

 

테스트 케이스가 여럿이고 범위는 1 ~ 5000으로 작지 않은 값이기 때문에,

해쉬 테이블을 구현하여 테스트 케이스가 테이블을 활용하는 방식으로 연산 자체를 줄였다.

 

이때 테이블에서의 table[n]은 'n 이하의 중복되지 않는 수의 갯수'를 갖게 했는데 

이 과정은 다이나믹 프로그래밍으로 메모리라이징된 이전 값을 참조하여 테이블에 값을 추가하도록 했다.

 

소스 코드

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

// 중복이 있는 수인지 아닌지 검증하기 위한 함수
// ex) 123 => true
// ex) 101 => false
const verify = (n) => {
  const set = new Set([...String(n)])
  return set.size === String(n).length
}  
 
// 테스트케이스에서 들어온 값들에서
// 테이블을 참조하여 start와 end사이 사용가능한 숫자들을 구하는 함수
const act = (el, table) => {
  const [start, end] = el.split(' ')
  // start === 1 인 경우, table[0]을 참조하게 되는데, 
  // 이때 해당 값은 undefined 이므로 없을 경우 0 을 사용하도록 했음
  // table[1]과 같이 table[0] = 0 으로 선언해도 무방
  return table[end] - (table[start - 1] || 0)
}

function solution(data) {
  const table = {}
  table[1] = 1
  
  // 검증 후 테이블 저장
  for(let i = 2 ; i <= 5000 ; i ++) {
    table[i] = table[i-1] + (verify(i) && 1)
  }
  
  const result = data.map(el => act(el,table))
  console.log(result.join('\n'))
}

solution(input)