[백준/G4] 1339 단어 수학

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

시간복잡도

O(N**2)

풀이

처음에는 단순히 알파벳마다 9~1까지 순서대로 가중치를 매겼는데 틀려서

다시 반례를 찾아보니 등장하는 각 자릿수마다 카운트를 해줘야 풀리는 문제였다.

예를 들어, 10의 자릿수에 알파벳 A가 10번 등장하면 100의 자릿수에 1번 등장한 다른 알파벳 B의 경우와 가중치가 같아지게 되고,
여기서 1의 자릿수에 한번이라도 등장하게 되면 A의 가중치가 B보다 조건 상 우선이 된다

(단어의 갯수 N은 최대 10)

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./1339.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = parseInt(input[0]);
const words = input
  .slice(1)
  .map((word) => word.trim())
  .sort((a, b) => b.length - a.length);

const weight = new Map();

//우선순위 부여
for (let i = 0; i < N; i++) {
  const word = words[i];
  const len = word.length;
  for (let j = 0; j < len; j++) {
    const char = word[j];
    // 각 자릿수 위치에 등장 횟수만큼 업데이트
    const posWeight = Math.pow(10, len - 1 - j);
    weight.set(char, (weight.get(char) || 0) + posWeight);
  }
}

// 가중치 순서대로 숫자 선정
const check = [...weight.entries()].sort((a, b) => b[1] - a[1]);
const numMap = new Map();
let num = 9;
for (const c of check) {
  numMap.set(c[0], num);
  num--;
}

// 숫자 계산
let ans = 0;
for (const word of words) {
  let wordVal = "";
  for (const a of word) {
    wordVal += numMap.get(a);
  }
  ans += parseInt(wordVal);
}

console.log(ans);

9360kb 96ms