[백준] 1339번 단어 수학 Javascript(NodeJs)

문제 링크

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

알고리즘: 그리디,브루트 포스

문제 요약

N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제. 단 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

풀이 요약

처음 브루트 포스로 접근하려 했지만. 모든 조합이 10! 이고 여기서 조금만 연산이 추가되면 시간제한이 걸릴 것 같은 느낌이 들었다. 그래서 다른 방법으로 풀어볼까 생각하면서 든 방법이 알파벳별로 각 단어의 자릿수에 맞게끔 더해줬다. 그러면 알파벳의 우선순위를 매길 수 있는데 값이 큰 알파벳부터 차례대로 9~0을 대입해주면 수의 합을 최대로 만들 수 있었다.

소스코드

const fs = require('fs');
let inputData = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let N = inputData[0].trim() * 1;
let alp_map = new Map();
for(let i=1; i<inputData.length; i++) {
    let input = inputData[i].trim().split('');
    for(let j=0; j<input.length; j++) {
        let pv = input.length - j //자릿수
        if(alp_map.get(input[j])===undefined) {
            alp_map.set(input[j], Number('1'.repeat(pv)));
        } else {
            alp_map.set(input[j], alp_map.get(input[j]) + Number('1'.repeat(pv)));
        }
    }
}
//map을 sort해줄려면 array 바꿔줘야함.
let alp_arr = Array.from(alp_map); //map을 array로 
alp_arr.sort((a,b) => b[1] - a[1]);
let sort_alp_map = new Map(alp_arr); //array를 map으로
let n = 9;
sort_alp_map.forEach((val,key) => {
    alp_map.set(key, n);
    n -=1;
});
let answel = 0;

for(let i=1; i<inputData.length; i++) {
    let input = inputData[i].trim().split('');
    let value = '';
    for(let j=0; j<input.length; j++) {
        value += alp_map.get(input[j]);
    }
    answel += Number(value);
}
console.log(answel);