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

문제

BOJ1339_단어 수학

풀이

완전탐색 (시간초과)

접근법이 떠오르지 않아서 처음엔 완전 탐색(순열)로 접근했다.

입력 조건에 "각 단어"가 아닌 "모든 단어"의 알파벳의 최대 개수는 10개라고 나와있길래 혹시 전체에서 알파벳의 개수가 총 10개일 수도 있겠다 싶기도 해서 완전 탐색으로 풀어봤는데 역시나 시간초과가 나왔다.

코드 (시간초과)

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const selected = Array(9).fill(false);
const alphabet = input.slice(1);
// 중복 제거를 위한 Set
const alphaSet = new Set();
alphabet.forEach((word) => {
    for (let c of word) {
        alphaSet.add(c);
    }
});

const setArr = Array.from(alphaSet); 
const obj = {};
setArr.forEach((c) => {
    obj[c] = null;
});

let answer = 0;
permutation(0);
console.log(answer);

function permutation(curIdx) {
    if (curIdx === setArr.length) {
        // 모든 알파벳에 숫자가 할당되었으면 계산
        answer = Math.max(answer, sum());
        return;
    }
    // 알파벳 마다 0~9까지의 숫자를 부여한다.
    for (let i = 0; i <= 9; i++) {
        if (selected[i]) continue;
        let curAlphabet = setArr[curIdx];
        obj[curAlphabet] = i;
        selected[i] = true;
        permutation(curIdx + 1);
        selected[i] = false;
        obj[curAlphabet] = null;
    }
}

function sum() {
    const numArr = [];
    alphabet.forEach((word, i) => {
        for (let c of word) {
            if (numArr[i]) {
                numArr[i] += obj[c].toString();
            } else {
                numArr[i] = obj[c].toString();
            }
        }
    });
    const result = numArr.reduce((acc, cur) => (acc += Number(cur)), 0);
    return result;
}

이로써 단어마다 알파벳의 최대 개수가 10개라는 뜻이 확실해졌으니 다른 접근법을 떠올려야 한다.

그리디

다른 접근법이 생각나지 않아서 다른 분의 블로그를 참고하여 풀었다.

이 문제는 각 알파벳의 자릿수에 10을 제곱하여 알파벳 별로 값을 누적해주고, 이를 내림차순으로 정렬한 뒤 큰 수부터 차례대로 9, 8, 7 ... 0 까지 곱해주어 최댓값을 구할 수 있다.

예를 들어 입력이 아래와 같이 주어졌다고 가정해보자.

3
GCF
ABCE
FAB

우선 우리는 각 알파벳의 자릿수에 10을 제곱해주어야 한다.

1. GCF
   • G : 100
   • C : 10
   • F : 1
2. ABCE
   • A : 1000
   • B : 100
   • C : 10
   • E : 1
3. FAB
   • F : 100
   • A : 10
   • B : 1

그리고 이를 알파벳 별로 누적하자

• A : 1010
• B : 101
• C : 20
• E : 1
• F : 101
• G : 100

최댓값을 구하기 위해선 큰 수부터 9, 8, 7, ... 0 순으로 곱해주어야 한다.

따라서 위의 누적한 값을 기준으로 내림차순 정렬을 해준다.

• A : 1010
• B : 101
• F : 101
• G : 100
• C : 20
• E : 1

그런다음 9부터 1씩 빼주며 누적값에 곱해준다.

• A : 9090
• B : 808
• F : 707
• G : 600
• C : 100
• E : 4

이를 전부 더해주면 11,309이고, 이 것이 주어진 단어로 만들 수 있는 최댓값이다.

이 알고리즘을 코드로 구현하면 아래와 같다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const words = input.slice(1);
const obj = {};
for (let word of words) {
    let len = word.length - 1; // 자릿수
    for (let c of word) {
        // 자릿수 만큼 10제곱
        if (obj[c]) obj[c] += 10 ** len;
        else obj[c] = 10 ** len;
        len -= 1;
    }
}

// 내림차순 정렬된 value 가져오기
const sorted = Object.values(obj).sort((a, b) => b - a);
let answer = 0;
let num = 9;
for (let value of sorted) {
    answer += value * num;
    num--;
}
console.log(answer);

참고

https://edder773.tistory.com/97