문제 개요

문제: 단어 수학

분류: 그리디 알고리즘

난이도: 골드4

문제 풀이

각 알파벳별로 가중치를 구한다.

모든 단어에 대해 일의 자리부터 높은 자리 순으로 각 알파벳에 1, 100, 1000, …과 같이 자릿 수를 누적하여 더한다.

예를 들어 AECE라는 단어가 있을 때 아래와 같이 더한다.

• 일의 자리 ‘E’ → alphabet[’E’] += 1
• 십의 자리 ‘C’ → alphabet[’C’] += 10
• 백의 자리 ‘E’ → alphabet[’E’] += 100
• 천의 자리 ‘A’ → alphabet[’A’] += 1000

그럼 최종적으로 ‘A’, ‘C’, ‘E’는 각각 1000, 101, 10이라는 가중치를 갖는다.

주어진 모든 단어에 대해 위를 수행하면 alphabet 배열에는 각 알파벳의 최종 가중치가 저장된다.
이 배열을 내림차순으로 정렬하면 가장 큰 가중치(=자릿 값)를 가진 수부터 정렬되기 때문에 앞에서부터 9, 8, 7, …을 곱하고 누적해서 더하면 정답이 된다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const [N, ...word] = fs.readFileSync(filePath).toString().trim().split("\n");

const solution = (N, word) => {
  const alphabet = new Array(26).fill(0);
  let answer = 0;

  for (let i = 0; i < +N; i++) {
    let num = 1;
    // 일의 자리부터 높은 자리 순으로 1, 100, 1000, ...씩 더한다.
    for (let j = word[i].length - 1; j >= 0; j--) {
      alphabet[word[i][j].charCodeAt(0) - 65] += num;
      num *= 10;
    }
  }

  alphabet.sort((a, b) => b - a);
  for (let i = 0; i < 9; i++) answer += alphabet[i] * (9 - i);

  console.log(answer);
};

solution(N, word);