[백준][그리디] 1339 단어수학 NodeJs 구현

     

목차

 

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

문제

 

 

문제 구현 방향

이 문제는 브루트포스로 풀면 당연히 시간초과가 난다...

최대 10! 순열까지는 괜찮았으나 순회하면서 값을 구하는 과정에서 시간복잡도가 더 초과한다.

 

 

잘못된 구현 방향

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let N = +input[0];

let arr = [];
let idx = 1;
let ans = 0;
let dic = new Map();

function total() {
  let sum = 0;
  for (let i = 0; i < N; i++) {
    let str = "";
    for (let j = 0; j < arr[i].length; j++) {
      str += String(dic.get(arr[i][j]));
    }
    console.log(str)
  }
  ans = Math.max(ans, sum);
}

function swap(a, b) {
  const array = Array.from(dic);
  let A = array[a][0];
  let B = array[b][0];
  let tmp = dic.get(A);
  dic.set(A, dic.get(B));
  dic.set(B, tmp);
}

function makePermutation(n, r, depth) {
  if (r === depth) {
    total();
    return;
  }
  for (let i = depth; i < n; i++) {
    swap(i, depth);
    makePermutation(n, r, depth + 1);
    swap(i, depth);
  }
  return;
}

//makePermutation(5, 5, 0);
let cnt = 9;
while (idx <= N) {
  let t = input[idx].trim();
  arr.push(t);
  idx++;
  console.log(t);
  for (let i = 0; i < t.length; i++) {
    if (!dic.has(t[i])) {
      dic.set(t[i], cnt);
      cnt--;
    }
  }
}

console.log(dic)
makePermutation(dic.size, dic.size, 0);

console.log(ans);

 

문제 풀이

이문제는 그리디로 자릿수로 최적해를 구하면 된다.

따라서 자릿수로 미리 계산해 주면 된다.

ex)

GDF

ACDEB

 

A -> 10000

C -> 1000

D -> 110

E -> 10

B -> 1

G -> 100

F -> 1

 

그 후 정렬해준뒤 9부터 차례대로 감소하면서 더하면 해결되는 문제였다.

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let N = +input[0];

let arr = [];
let idx = 1;

let dic = new Map();

while (idx <= N) {
  let t = input[idx].trim();
  arr.push(t);
  idx++;
  let mul = t.length-1;
  for (let i = 0; i < t.length; i++) {
    let value = Math.pow(10, mul);
    mul--;
    if (!dic.has(t[i])) {
      dic.set(t[i], value);
    } else {
      dic.set(t[i], dic.get(t[i]) + value);
    }
  }
}
let Dic = Array.from(dic);
Dic.sort((a, b) => b[1] - a[1]);
let ans = 0;
let cnt = 9;

Dic.forEach((item) => {
  ans += item[1] * cnt;
  cnt--;
});
console.log(ans);