백준 알고리즘 - 1339 단어 수학 (JAVA)

 

1339번: 단어 수학

문제

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

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

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

입력

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

채점 결과

코드

import java.io.*;
import java.util.*;
import java.lang.Math;

public class Main {
    static HashMap<String,Integer> map=null;
    static int result=0;
    static int value=9;
    public static void main(String[] args) throws NumberFormatException, IOException {
    	
    	map=new HashMap<String,Integer>();
    	// 콘솔 입력 시 BufferedReader 객체 생성
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int n=Integer.parseInt(br.readLine());
    	
        // N 개의 단어 입력받기
    	for(int i=0;i<n;i++) {
    		String temp=br.readLine();
    		int x=0;
            // 단어별 알파벳의 자리수를 Map에 저장하기. ex) ABA -> A:101 , B:10으로 저장함
    		for(int j=temp.length()-1;j>=0;j--){
                // 일의자리 부터 계산
                int q=(int)Math.round(Math.pow(10,x)); 
                if(!map.containsKey(temp.charAt(j)+"")){
                    map.put(temp.charAt(j)+"",q);                   
                }else{
                	int prev=map.get(temp.charAt(j)+"");
                	int ff=prev+q;
                    map.put(temp.charAt(j)+"",ff);
                }
                x=x+1;  
            }
    	}
    	// 맵을 전체 출력 한번 해봤음
    	Iterator<String> mapIter = map.keySet().iterator();
        while(mapIter.hasNext()){
            String key = mapIter.next();
            int value = map.get(key);
        }
        // Map을 value기준으로 정렬해서. value가 제일 큰 알파벳을 9로 지정한다. 9->8->7순
        List<String> keySetList = new ArrayList<>(map.keySet());
        // 내림차순
		Collections.sort(keySetList, (o1, o2) -> (map.get(o2).compareTo(map.get(o1))));
		for(String key : keySetList) {
            result+=map.get(key)*value;
            value--;
		}
        System.out.println(result);
    	
    }
 
}

로직

 일단, 입력 데이터가 여러줄이라서 StringBuffer로 입력받았고 HashMap을 사용했습니다. 문제에서 요구한 단어의 총합이 최대가 되는 걸 구하기 위해서는, 가장 잘 쓰이는 수부터 9를 할당해야 겠다고 생각했습니다. 이때 가장 잘 쓰이는 것의 기준은 수학 덧셈할 때처럼 생각했습니다.  예를들어 ABA 라는 단어가 있다고 하면 A는 100+1, B는 10으로 계산을 했습니다. 이것을 HashMap<String, Integer>형태로 저장했고, value기준으로 정렬해서 결과 값을 계산했습니다.

 

도움이 되셨다면 왼쪽 하단에 하트 ♥ 한번 눌러주세요 :)