백준 1339 단어 수학

문제

단어 수학 문제를 푸는데 단어끼리 더해서 가질 수 있는 합을 최대로 만드는 문제이다. 이 문제의 경우 각 자릿수가 큰 값을 기준으로 9부터 할당해야 하므로 그리디 문제라고 볼 수 있겠다. 그냥 각 값이 가지는 자릿수를 가중치처럼 다루면서 누적 가중치로 내림차순 정렬하고, 해당 정렬 순으로 9부터 순서대로 할당하여 계산하면 된다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const n = +inputs[0];
 
const wordMap = {};
 
for (let i = 1; i <= n; i++) {
  const alphabets = inputs[i].split("");
  let temp = alphabets.length - 1;
  for (let j = 0; j < alphabets.length; j++) {
    wordMap[alphabets[j]]
      ? (wordMap[alphabets[j]] += Math.pow(10, temp))
      : (wordMap[alphabets[j]] = Math.pow(10, temp));
    temp--;
  }
}
const sortedWordMap = Object.entries(wordMap).sort((a, b) => b[1] - a[1]);
 
let max = 9;
let acc = 0;
for (let i = 0; i < sortedWordMap.length; i++) {
  acc += sortedWordMap[i][1] * max;
  max--;
}
console.log(acc);