백준 - 1339 단어 수학(Java)

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

1339번: 단어 수학

 

그리디 문제입니다.

 

단어의 위치에 따라 가중치를 더해 가장 큰 가중치를 가진 문자부터 숫자를 할당하면 됩니다.

 

말로만 하면 이해가 힘드니 예시로 보겠습니다.

/*
 'A'~'Z'는 0~9의 숫자이므로 각 일의 자리라 생각했을 때, 아래 주석과 같은 다항식이 나옵니다.
*/

10
ABB // 1. 100*A + 10*B + 1*B
BC // 2. 10*B + 1*C
BC // 3. 10*B + 1*C
BC // 4. 10*B + 1*C
BC // 5. 10*B + 1*C
BC // 6. 10*B + 1*C
BC // 7. 10*B + 1*C
BC // 8. 10*B + 1*C
BC // 9. 10*B + 1*C
BC // 10. 10*B + 1*C

 

1번은 A에 100, B에는 10과 1의 가중치를 더합니다.

 

2번은 B에 10, C에 1의 가중치를 더합니다.

 

3번은 2번과 같습니다.

 

4번부터 마지막 10번 역시 2번과 같아 다름과 같은 결과가 나옵니다.

위 결과를 바탕으로

B의 가중치 크기가 첫 번째니 9를 할당합니다.

A의 가중치 크기가 두 번째니 8을 할당합니다.

C의 가충치 크기가 세 번째니 7을 할당합니다.

그리면 899 + 97*7 = 1772로 최대가 됩니다.

 

[구현 코드]

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

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

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

        int[][] weights = new int[26][2];
        int[] values = new int[26];
        List<String> words = new ArrayList<>();

        for (int i = 0; i < 26; i++) {
            weights[i][0] = i;
        }

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            words.add(str);

            for (int j = 0; j < str.length(); j++) {
                weights[str.charAt(j)-'A'][1] += Math.pow(10, str.length()-j-1);
            }
        }

        Arrays.sort(weights, (o1, o2) -> o2[1] - o1[1]);

        int allocate = 9;
        for(int i=0; i<26; i++){
            if(weights[i][1] > 0){
                values[weights[i][0]] = allocate--;
            }else{
                break;
            }
        }

        int answer = 0;
        for (String word : words) {
            int sum = 0;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                sum += Math.pow(10, word.length()-i-1) * values[c - 'A'];
            }
            answer += sum;
        }

        bw.write(String.valueOf(answer));

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