백준 1339: 단어 수학 - javascript(그리디)

문제 출처 

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

 

문제 풀이 

이건 정말 아이디어가 필요했다. 

난 정~ 말 복잡하게 풀었었는데, 해법을 보고 머리를 탁 ~ 쳤다 ! 

앞으로 비슷한 문제가 있다면 이런 접근을 활용해야 겠다  

 

이 문제는 사실 두개를 고려해야 하는데 

우선순위가 높을 수록 높은 숫자를 받는 것이라고 할 때, 

- 높은 자리에 있을 수록 (십의 자리 > 일의 자리) 우선순위가 올라간다. 

- 빈번하게 나타날 수록 (만약 십의 자리에 있는 문자가 'A', 'B'가 있을 때, 만약 A가 일의 자리에 B보다 더 많이 나타났다면)우선순위가 올라간다.

 

이 복잡한 셈처럼 보이는 것이 아주 ~ 간단한 아이디어로 쉽게 풀린다. 

 

"각 문자를 돌면서 해당 문자가 있는 자리수를 계속 더해주는 것이다. "

 

예를 들어, 

{A : 0}

_ _ A : A가 1의 자리 수에 있을 때  1을 더한다. 

_ A _ : A가 10의 자리 수에 있을 때 10을 더한다. 

A _ _ : A가 100의 자리 수에 있을 때 100을 더한다. 

 

그럼 이 모든 숫자를 더한 값은 111이 된다. 

{A : 111} 

 

 만약 다른 문자는 아래와 같다면? 

{B: 100}

{C: 1001}

 

자, 숫자가 큰 순서대로 9부터 할당하면 된다. 

C : 9

A : 8

B : 7 

 

문제에서 모든 값을 더하라 했으니, 

 

C: 9 * 1001 

A : 8 * 111

B: 7 * 100

 

이 모든 값을 더해서 return 하면 끝 !!! 

 

정답 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const n = Number(input.shift())
let arr = []; 
for(let i=0; i<n; i++){
    arr.push(input[i])
}
function solution(n, arr){
    let map = new Map(); 
    
    for(let word of arr){
        let cnt = 1
        for(let i=word.length-1; i>=0; i--){
            if(!map.has(word[i])){
                map.set(word[i], 0)
            }
          map.set(word[i], map.get(word[i])+cnt)
            cnt *= 10 
        }
    }
    let answer = [...map.entries()]
    answer.sort((a,b) => b[1] - a[1])
    let num = 9
    let totalSum = 0; 

    for(let [key, value] of answer){
        totalSum += value * num
        num--; 
    }
    return totalSum; 
}
console.log(solution(n, arr))