두 번째 푸는 거지만 풀이가 바로 생각이 안나서 속상하다..
단어 수학 문제 풀이의 핵심은 각 알파벳에 어떤 수를 넣어야 가장 큰 수가 될수 있는지 찾는 것이다.
알파벳이 가지는 자릿수의 합이 클수록 더 큰 수로 치환해서 값을 구해야한다.
예를 들어 주어진 식이 GCF + ACDEB
일 때
위의 사진처럼 각 알파벳이 가지는 자릿수의 합을 구해준다.
자릿수의 합은 Map을 통해 저장해주었다.
그런 다음 map의 values를 리스트에 저장하고 내림차순으로 정렬한다.
내림차순으로 정렬함으로써 value가 가장 큰 값에 순차적으로 적용할수 있는 큰 값 9부터 곱해가며 최대의 값을 구할수 있기 때문이다.
처음에 헤맸던 이유가 알파벳과 value값을 연관지어 끝까지 가져가려고 했었는데 생각해보니 알파벳은 알 필요가 없다. 0~9까지의 수를 value에 적용했을때 가장 큰값을 구하는 것이기 때문에 value값만 가져가 연산을 수행하면 어떤 알파벳이 value가 같은 값을 가지든 상관이 없다는 얘기다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
public class 단어수학 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
HashMap<String, Integer> map = new HashMap<>();
int N = Integer.parseInt(br.readLine());
for(int i=0;i<N;i++){
StringBuilder sb = new StringBuilder(br.readLine());
//단어를 역전 시켜놓으면 알파벳의 index를 10의 index로 알파벳이 가지는 자릿수를 쉽게 구할수 있다.
sb.reverse();
String[] word = sb.toString().split("");
for(int j=0;j<word.length;j++){
//map을 사용함으로써 문제에서 주어진 알파벳과 자릿수의 합을 중복없이 저장할수있다.
map.put(word[j],map.getOrDefault(word[j],0)+(int)Math.pow(10,j));
}
}
List<Integer> valueList = new ArrayList<>(map.values());
//자릿수의 합 내림차순
Collections.sort(valueList, new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2){
return o2-o1;
}
});
int v = 9;
int sum = 0;
for(int value : valueList){
sum += value*v;
v--;
}
bw.write(String.valueOf(sum));
bw.flush();
bw.close();
}
}
처음에 풀었던 것보다 시간이 단축되어서 이전 코드를 확인해봤더니, 이전에는 주어지는 단어를 역전해서 배열에 따로 저장해놨다가 다시 역전한 단어 배열을 돌면서 map에 저장해주고 있었다.
N번만큼의 반복문이 더 있었는데 한 번의 반복문으로 Map에 자릿수를 저장해주었고 Map에 저장하는 방법도 map.getOrDefault()메소드를 통해 코드가 깔끔해졌다. 이런거보면 뿌듯하다 :)