BOJ - 1339 단어 수학

Problems

---

Solves

두 번째 푸는 거지만 풀이가 바로 생각이 안나서 속상하다..
단어 수학 문제 풀이의 핵심은 각 알파벳에 어떤 수를 넣어야 가장 큰 수가 될수 있는지 찾는 것이다.
알파벳이 가지는 자릿수의 합이 클수록 더 큰 수로 치환해서 값을 구해야한다.
예를 들어 주어진 식이 GCF + ACDEB 일 때

위의 사진처럼 각 알파벳이 가지는 자릿수의 합을 구해준다.

자릿수의 합은 Map을 통해 저장해주었다.

그런 다음 map의 values를 리스트에 저장하고 내림차순으로 정렬한다.
내림차순으로 정렬함으로써 value가 가장 큰 값에 순차적으로 적용할수 있는 큰 값 9부터 곱해가며 최대의 값을 구할수 있기 때문이다.
처음에 헤맸던 이유가 알파벳과 value값을 연관지어 끝까지 가져가려고 했었는데 생각해보니 알파벳은 알 필요가 없다. 0~9까지의 수를 value에 적용했을때 가장 큰값을 구하는 것이기 때문에 value값만 가져가 연산을 수행하면 어떤 알파벳이 value가 같은 값을 가지든 상관이 없다는 얘기다.

---

Code

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();
	}
}

---

Result

처음에 풀었던 것보다 시간이 단축되어서 이전 코드를 확인해봤더니, 이전에는 주어지는 단어를 역전해서 배열에 따로 저장해놨다가 다시 역전한 단어 배열을 돌면서 map에 저장해주고 있었다.
N번만큼의 반복문이 더 있었는데 한 번의 반복문으로 Map에 자릿수를 저장해주었고 Map에 저장하는 방법도 map.getOrDefault()메소드를 통해 코드가 깔끔해졌다. 이런거보면 뿌듯하다 :)