단어 수학
📚 문제 설명
N 개의 단어가 주어지고 각각의 단어는 알파뱃으로 이루어져 있다.
각각의 알파뱃에 0부터 9까지의 숫자를 중복되지 않게 부여한다고 했을 때, 두 수의 합이 최대가 되게 하라.
예를 들어 2개의 단어 "ABC", "DF" 가 주어진다면, A = 9, B = 9, C = 7, D = 6, F = 5 일 때,
987 + 65 = 1052 으로 최댓값을 가질 것이다.
👨🏻💻 풀이 과정
이 문제는 2번 풀게 되었는데 첫번째 풀이는 나도 왜 이렇게 풀었는지 모르겠다.
다시는 이런 실수를 하지 않기 위해 첫번째 풀이부터 이 글을 작성하고자 한다.
💡공통 부분
각각의 알파벳에 어떤 숫자를 부여하느냐가 이 문제의 가장 핵심일 것이다.
따라서 각각의 단어에 따라 알파벳에 값을 저장하기로 했다.
위의 "ABC", "DF"를 예시로 들면,
let obj = {
"A":100,
"B":10,
"C":1,
"D":10,
"F": 1
}
알파벳 객체 저장
let AlphaOBJ = {};
for (let i = 0; i < N; i++) {
let word = input[i];
for (let j = word.length - 1; j >= 0; j--) {
AlphaOBJ[word[j]] = AlphaOBJ[word[j]] ? AlphaOBJ[word[j]] + 10 ** (word.length - j - 1) : 10 ** (word.length - j - 1);
}
}💡첫번째 풀이
이 후 알파벳의 값이 큰 순서대로 9부터 차례대로 값을 부여하면 될 것이다.
그래서 객체의 모든 값을 우선 순위큐에 넣기로 했다.
전체 로직은 다음과 같다.
AlphaOBJ의 모든 값을PQ에 삽입.PQ에서 값을 하나씩 빼주며 9부터 차례로 부여.- 각각의 단어들에 맞게 숫자 생성.
- 각각의 숫자를 합하여 정답 출력.
solution 함수
class MaxHeap {
//생략
}
const solution = () => {
const PQ = new MaxHeap();
for (const alphaOBJKey in AlphaOBJ) {
PQ.Insert([alphaOBJKey, AlphaOBJ[alphaOBJKey]]);
}
let num = 9;
while (PQ.GetLength() !== 0) {
const [Target, Value] = PQ.Pop();
AlphaOBJ[Target] = num;
num--;
}
let answer = 0;
for (let i = 0; i < N; i++) {
let NumString = '';
for (let j = 0; j < input[i].length; j++) {
NumString += `${AlphaOBJ[input[i][j]]}`;
}
answer += parseInt(NumString);
}
console.log(answer);
};
solution();
전체 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const N = parseInt(input.shift());
let AlphaOBJ = {};
// 각각의 알파벳이 나온 횟수 갱신.
for (let i = 0; i < N; i++) {
let word = input[i];
for (let j = word.length - 1; j >= 0; j--) {
AlphaOBJ[word[j]] = AlphaOBJ[word[j]] ? AlphaOBJ[word[j]] + 10 ** (word.length - j - 1) : 10 ** (word.length - j - 1);
}
}
// 우선 순위 큐
class MaxHeap {
constructor() {
this.heap = [null];
}
Insert(item) {
let cur = this.heap.length;
while (cur > 1) {
const Parent = Math.floor(cur / 2);
if (this.heap[Parent][1] < item[1]) {
this.heap[cur] = this.heap[Parent];
cur = Parent;
}else break;
}
this.heap[cur] = item;
}
Pop() {
if (this.heap.length > 2) {
const PopItem = this.heap[1];
this.heap[1] = this.heap.pop();
let cur = 1;
let Left = cur * 2;
let Right = cur * 2 + 1;
while (this.heap[Left]) {
let Compare = Left;
if (this.heap[Right] && this.heap[Right][1] > this.heap[Left][1]) {
Compare = Right;
}
if (this.heap[Compare][1] > this.heap[cur][1]) {
[this.heap[Compare], this.heap[cur]] = [this.heap[cur], this.heap[Compare]];
cur = Compare;
Left = cur * 2;
Right = cur * 2 + 1;
}else break;
}
return PopItem;
}else if (this.heap.length === 2) {
return this.heap.pop();
} else {
return null;
}
}
GetLength() {
return this.heap.length - 1;
}
Test() {
console.log(this.heap);
}
}
const solution = () => {
const PQ = new MaxHeap();
for (const alphaOBJKey in AlphaOBJ) {
// [키, 값] 삽입.
PQ.Insert([alphaOBJKey, AlphaOBJ[alphaOBJKey]]);
}
// 9부터 순차적으로 부여.
let num = 9;
while (PQ.GetLength() !== 0) {
const [Target, Value] = PQ.Pop();
AlphaOBJ[Target] = num;
num--;
}
let answer = 0;
for (let i = 0; i < N; i++) {
let NumString = '';
for (let j = 0; j < input[i].length; j++) {
// 단어 앞부터 하나씩 숫자로 변경.
NumString += `${AlphaOBJ[input[i][j]]}`;
}
// 완성된 숫자를 더해줌.
answer += parseInt(NumString);
}
console.log(answer);
};
solution();
💡두번째 풀이
첫번째 풀이를 풀고나서 다른 JavaScript 정답자들의 코드수를 보니 내가 압도적으로 많았다.
그래서 코드를 다시 살펴보니 여러 문제들이 있었다.
- 우선순위 큐는 불필요하다.
- 불필요한 문자열 계산이 있다.
우선 첫번째로 바로 객체에서 Object.entries.sort()를 이용해 크기순으로 정렬하면 되기 때문에 우선 순위 큐는 굳이 필요하지 않다.
그럼 코드는 다음과 같이 수정된다.
수정 1
//전체 PQ 제거.
// entries 함수를 이용해 객체를 [키,값]으로 이용하여 sort() 사용.
AlphaOBJ = Object.entries(AlphaOBJ).sort((a, b) => b[1] - a[1]);두번째로 이미 단어를 돌며 각각의 단어에서의 알파벳의 위치에 따라 단위 계산까지 하여 객체에 저장 했기 때문에 굳이 알파벳에 각각 9를 새로 부여하고 단어를 바꿔주는 과정은 불필요하다.
이미 AlphaOBJ는 내림차순으로 정렬된 상태이기 때문에 바로 값을 9부터 차례로 곱하여 더해주면 된다.
수정 2
let AssignNum = 9;
let answer = 0;
// 내림차순으로 정렬된 배열 순차적으로 확인.
for (const alphaOBJElement of AlphaOBJ) {
const [Target, Value] = alphaOBJElement;
// 바로 계산.
answer += Value * AssignNum;
AssignNum--;
}그렇게 수정한 전체 풀이는 아주 간결해졌다.
수정 후 전체 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const N = parseInt(input.shift());
let AlphaOBJ = {};
// 알파벳 값 부여.
for (let i = 0; i < N; i++) {
let word = input[i];
for (let j = word.length - 1; j >= 0; j--) {
AlphaOBJ[word[j]] = AlphaOBJ[word[j]] ? AlphaOBJ[word[j]] + 10 ** (word.length - j - 1) : 10 ** (word.length - j - 1);
}
}
// 알파벳 객체 정렬
AlphaOBJ = Object.entries(AlphaOBJ).sort((a, b) => b[1] - a[1]);
let AssignNum = 9;
let answer = 0;
for (const alphaOBJElement of AlphaOBJ) {
const [Target, Value] = alphaOBJElement;
// 크기 순으로 차례로 계산.
answer += Value * AssignNum;
AssignNum--;
}
console.log(answer);
🧐 후기
지금 와서 봐도 어쩌다가 첫번째 풀이에서 저런 풀이를 생각했는지 부끄러워진다.
아무래도 우선순위큐 문제를 풀며, sort() 함수 사용을 최대한 자제하다보니 무의식 중에 sort()를 고려하지 않고 코드를 작성한 것 같다.
