백준 1339 단어 수학

문제

제한 사항

입출력 예

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const sol = (input) => {
  const n = +input.shift();
  let obj = {};
  for (let str of input) {
    let tenDigit = 1;
    for (let i = str.length - 1; i >= 0; i--) {
      let cur = str[i];
      if (obj[cur]) {
        obj[cur] += tenDigit;
      } else {
        obj[cur] = tenDigit;
      }
      tenDigit *= 10;
    }
  }
  const sortedArr = Object.entries(obj).sort((a, b) => b[1] - a[1]);

  let maxNum = 9;
  let sum = 0;
  for (let i = 0; i < sortedArr.length; i++) {
    sum += sortedArr[i][1] * maxNum;
    maxNum--;
  }
  return sum;
};

console.log(sol(input));

• 그리디
• 단어에서 위치한 알파벳들의 자릿수 합을 계산하고, 자릿수의 합 순으로 정렬한다. 자릿수의 합이 큰 알파벳부터 순차적으로 가능한 가장 큰 숫자를 대입한다.
• "AAA", "BCD"일 때 111A + 100B + 10C + D 가되고
  순서대로 9,8,7,6 을 대입하면 최대값이 된다.

복습

const sol = (n, input) => {
  const obj = {};

  for (let str of input) {
    let ten = 1;
    for (let s of str) {
      if (obj[s]) {
        obj[s] += ten;
      } else {
        obj[s] = ten;
      }
    }
    ten *= 10;
  }

  const sortedArr = Object.entries(obj).sort((a, b) => b[1] - a[1]);

  let max = 9;
  let sum = 0;

  for (let [key, value] of sortedArr) {
    sum += value * max;
    max--;
  }

  return sum;
};