[백준] 단어 수학 1339번 (Java)

출처 : https://www.acmicpc.net/problem/1339

1339번: 단어 수학

풀이 방법

그리디로 풀어야 한다. 

가장 큰 수를 만들기 위해 각 알파벳 자릿수를 계산해서 큰 거부터 9를 할당해 주면 된다.

알바벳을 계산할 때 제일 왼쪽부터 10을 곱하면서 계산하면 된다.

 

import java.io.*;
import java.util.*;
public class Main {
    static int N;    
    static int[] alphabet = new int[26]; 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr;
        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            inputStr = br.readLine();
            int temp = 1;
            for (int j = inputStr.length()-1; j >= 0 ; j--) {
                char c = inputStr.charAt(j);
                alphabet[c-'A'] += temp; //알파벳이 발생하면 더해준다.
                temp = temp*10;
            }
        }
        Arrays.sort(alphabet); // 내림차순으로 정렬
        int ans = 0;
        int num = 9;
        for (int i = 25;i > 0;i--) {
            if(alphabet[i] == 0) { // 0이면 포함되지 않았음
                break;
            }
            ans += alphabet[i] * num; //9부터 할당해 주기
            num--;
        }

        System.out.print(ans);
    }
}