Baekjoon_1339_단어 수학

문제 설명

1339번: 단어 수학

• 주어지는 수는 알파벳으로 이루어져있음
• 알파벳 당 한자리 숫자(9~0) 할당
  • EX. ABC  =>  A = 9, B = 8, C = 7  =>  987

=> 주어지는 알파벳 수의 합의 최대값 출력

 

 

문제 풀이

이 문제를 보고 처음 생각한 풀이 방법은 높은 자리에 있는 알파벳에 높은 숫자를 할당하는 방식이었다.

 

하지만 이 방식은 틀린 방식이었다. 예를 들어 AB + BB + BB 의 연산이 있을 경우 A에 9, B에 8을 할당한 것보다 A에 8, B에 9를 할당하는 것이 더 큰 계산결과가 나오기 때문이다.

 

그 후 생각한 풀이 방법은 각 알파벳의 자리수 값을 다 더하는 것이었다.

 

이 문제에서는 모든 수의 합을 구하기 때문에 ABC + DE 와 ADE + BC의 계산 결과는 같다.

 

따라서 ABC => A = 100, B = 10, C = 1, DDE => D = 110, E = 1처럼 자리수 값을 (알파벳, 자리수의 합)으로 저장하고, 이 중 자리수의 합 값이 큰 순서대로 큰 수를 할당했다.

 

문제 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Iterator;
import java.util.PriorityQueue;

public class _1339_단어수학 {
	static class Node implements Comparable<Node>{
		char alpha;
		int num;
		
		Node(char alpha, int num){
			this.alpha = alpha;
			this.num = num;
		}
		
		@Override
		public int compareTo(Node o) {
			return o.num - this.num;
		}

	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		HashMap<Character, Integer> map = new HashMap<>();
		char[][] strings = new char[N][];
		
		for (int i = 0; i < N; ++i) {	//각 알파벳의 자리값 계산 
			strings[i] = in.readLine().toCharArray();
			int pos = strings[i].length - 1;
			for (int j = 0; j < strings[i].length; ++j) {
				int num = map.containsKey(strings[i][j])?map.get(strings[i][j]):0;	//이미 저장된 값이면 저장된 것 가져오기, 아니면 0
				map.put(strings[i][j], num + (int)Math.pow(10, pos--));	//자릿수 값 더해서 해시맵에 넣기
			}
		}
		
		PriorityQueue<Node> pq = new PriorityQueue<>();
		Iterator<Character> iter = map.keySet().iterator();
		while(iter.hasNext()) {	//알파벳과 자리값 정보 가지는 Node를 우선순위 큐에 넣어서 정렬
			char alpha = iter.next();
			int num = map.get(alpha);
			pq.add(new Node(alpha,num));
		}
		
		int num = 9;
		while(!pq.isEmpty()) {	//자리값이 큰 알바벳부터 큰 수 할당
			Node n = pq.poll();
			map.put(n.alpha, num--);
		}
		
		int sum = 0;
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; ++i) {	//할당받은 수에 따른 계산 수행
			for (int j = 0; j < strings[i].length; ++j) {
				sb.append(map.get(strings[i][j]));
			}
			sum += Integer.parseInt(sb.toString());
			sb.setLength(0);
		}
		
		System.out.println(sum);
		
		
	}
}