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

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

1339번: 단어 수학

 

1. 문제 설명

 

알파벳 대문자로만 이루어진 N개의 단어가 주어질 때, 각 알파벳을 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합할 때 최댓값을 구하는 문제.

 

* 두 개 이상의 알파벳이 같은 순서로 바뀌어지면 안된다.

 

2. 풀이

 

ABCD, ABC라는 2개의 단어가 주어졌다고 하자. 이를 더한다고 하면

ABCD+ABC= A*1000+B*100+C*10+D+A*100+B*10+C= A*1100 + B*110 + C*11 + D로 표현할 수 있다.

 

곱해진 값이 큰 순서대로 알파벳을 높은 수로 바꾸면 그것이 최대합이다.

 

따라서 단어가 주어질 때 문자열을 곱하는 수를 더하고 후에 정렬하여

 

곱해진 값이 큰 수부터 큰 값으로 바꾸는 식으로 답을 구하면 된다.

 

 

*로직

- 입력받은 문자열을 A*100+B*10.. 식으로 분해하여 각 문자에 곱해진 값들을 저장한다.

- 곱해진 값이 작은 순서대로 정렬

- 곱해진 값이 큰 것부터 시작하여 곱해진 값(alpha [x])과 바꾸는 수(x-16)를 곱해서 답에 더한다.

 

 

3. 코드

import java.awt.*;
import java.io.*;
import java.util.*;

public class Main {

    public static int[] alpha = new int[26];


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        for (int x = 0; x < N; x++) {
            String line = br.readLine();

            int size = line.length();

            int base = (int) Math.pow(10, size - 1);

            for (int y = 0; y < size; y++) {
                alpha[line.charAt(y) - 'A'] += base;
                base /= 10;
            }
        }

        Arrays.sort(alpha);

        int ans = 0;

        for (int x = 25; x >= 17; x--) {
            ans += alpha[x] * (x - 16);
        }

        System.out.println(ans);


    }


}