[백준] 1339번 : 단어 수학 - JAVA [자바]

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

---

그리디 알고리즘 문제이다.

가장 높은 자리에 배정 받은 알파벳부터 숫자 9를 배정 받아야 가장 큰 합을 만들 수 있다.

그러면 일단 각 알파벳의 자리를 알아야 한다.
알파벳은 총 26이므로 배열을 생성한다.

int[] alphabet = new int[26];
int position = 1;
for (int j = charArray.length - 1; j >= 0; j--) {
	alphabet[charArray[j] - 'A'] += position;
    position *= 10;
}

입력 받은 문자열의 제일 뒤부터 1의 자리 수(position)에 위치한 알파벳이라는 것을 저장한다.

그 다음 자릿수는 position *= 10; 을 해주어서 자릿 수를 저장한다.

이때 주의할 점이 하나 있다. 만약 중복된 알파벳이 나오면(AA) A 의 자릿수가 1의 자리 수였다가 두 번째 A 를 처리할 때 10의 자리수로 저장된다. 이를 방지하기 위해 +=를 해주어서 A의 자리수는 11로 저장된다. 즉, 10의 자리수와 1의 자리수에 나온다는 뜻이다.

그 후 배열을 정렬하고 큰 수부터 9 부터 -1 하면서 곱하여 합을 구하면 된다.

예를 들어 AAA에 대해서 배열의 A 에는 111이 저장되고 이 수가 배열에서 가장 크므로 111 * 9 = 999 가 된다.

혹은

2
AAA 
BBB

입력에 대해서는 A에는 111 x 9 = 999가 되고 그 다음 B는 111 x 8 = 888 이 되어 답은 999 + 888 이 된다.

---

public class bj1339 {

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] alphabet = new int[26];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            char[] charArray = line.toCharArray();
            int position = 1;
            for (int j = charArray.length - 1; j >= 0; j--) {
                alphabet[charArray[j] - 'A'] += position;
                position *= 10;
            }
        }

        Arrays.sort(alphabet);
        int index = 9;
        int sum = 0;
        for (int i = alphabet.length - 1; i >= 0; i--) {
            if (alphabet[i] == 0) {
                break;
            }
            sum += alphabet[i] * index;
            index--;
        }


        bw.write(sum + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}