[백준] 1339. 단어수학 / Java

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

1339번: 단어 수학

---

문제 풀이

알파벳에 0~9 사이의 수를 대입하여 가장 큰 수를 만드는 문제이다.

핵심은 높은 자릿수에 위치한 알파벳에 큰 수를 맵핑하는 것이다.

 

예를 들어 아래 두 단어가 주어졌을 때,

GCF
ACDEB

알파벳별로 따로따로 생각해보면 다음과 같다.

GCF = 100*G + 10*C + 1*F

ACDEB = 10000*A + 1000*C + 100*D + 10*E + 1*B

 

그 다음으로는

알파벳 길이만큼의 배열 alphabets[]를 생성하여 각 알파벳에 해당하는 인덱스에 앞서 구한 10^n의 값들을 누적합한다.

A	B	C	D	E	F	G	H	I	...
10000	1	1000	100	10	1	100	0	0	...

이제 저장된 수가 큰 알파벳부터 9~0의 수를 할당하면 총합의 최댓값을 구할 수 있다.

 

소스 코드

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class BOJ1339 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        String[] words = new String[N];  // 입력받은 문자들
        int[] alphabets = new int[26];  // 알파벳 갯수만큼의 길이를 가진 배열

        for (int i = 0; i < N; i++) {
            words[i] = sc.next();
        }

        for (String word : words) {
            int temp = (int) Math.pow(10, word.length() - 1);  // 자릿수
            for (int i = 0; i < word.length(); i++) {
                alphabets[(int)word.charAt(i) - 65] += temp;
                temp /= 10;
            }
        }

        Arrays.sort(alphabets);  // 오름차순 정렬
        int digit = 9;
        int sum = 0;

        // 큰 수를 가진 알파벳에 9부터 차례로 수를 부여한다
        for (int i = alphabets.length-1; i >= 0; i--) {
            // 정렬했으므로 0이 나왔으면 더 볼것도 없다
            if (alphabets[i] == 0) {
                break;
            }

            sum += alphabets[i]*digit;
            digit--;
        }

        System.out.println(sum);
    }

}