[BOJ] 1339 단어 수학 - JAVA

1. 문제

1339번: 단어 수학

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

---

2. 풀이

import java.io.*;
import java.util.*;

public class BOJ_1339_단어수학 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      Map<Character,Integer> map = new HashMap<>();

      char[] word;
      for(int i=0;i<N;i++){
         word = in.readLine().toCharArray();
         int value = (int)Math.pow(10,word.length-1);
         for(int j=0;j<word.length;j++) {
            map.put(word[j], map.getOrDefault(word[j],0)+value);
            value /= 10;
         }
      }

      //value 기준 내림차순정렬
      List<Character> keySet = new ArrayList<>(map.keySet());
      keySet.sort((o1,o2)->map.get(o2)-map.get(o1));

      int answer = 0;
      int number = 9;
      for(Character ch:keySet){
         answer += number*map.get(ch);
         number--;
      }

      System.out.println(answer);
   }
}

---

3. 결과

처음에 Math.pow를 매번했는데, /10을 반복하는 방식으로 바꿨더니 시간과 메모리가 조금 덜 들었다.