그리디. 단어 수학

문제

10개의 알파벳, 최대 8자리의 알파벳 대문자가 주어지고, 이를 숫자 더하듯이 더해서 가장 큰 수를 만드는 문제이다.

해결방향성

우선 자릿수가 중요해보인다. 단어에 사용한 알파벳들을 체크하고, 숫자 더하듯이 계산하기위해, 알파벳마다 자릿수를 매긴다. 자릿수는 각 문자열 길이 - 자릿수 인덱스. 이렇게 int[] 배열에 각 알파벳의 값을 대입하면, A = 10000, B = 1000, C = 110 처럼, 중복되는 알파벳 사용도 가장 큰 수 순으로 대입할수있다. 마지막으로 9부터 하나씩 내려가면서 자릿수에 곱해준다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

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

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

        // 단어 입력 받기
        String[] word = new String[N];
        for (int i = 0; i < N; i++) {
            word[i] = br.readLine();
        }

        // 어떤 알파벳이 들어갔는지 체크하기
        boolean[] alpha = new boolean[26];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < word[i].length(); j++) {
                int index = word[i].charAt(j) - 'A';
                alpha[index] = true;
            }
        }
        // 속한 알파벳 모두 true

        int[] intalpha = new int[26];
        for (int i = 0; i < 26; i++) {
            if (alpha[i]) {
                for (int j = 0; j < N; j++) {
                    for (int k = 0; k < word[j].length(); k++) {
                        if (i == word[j].charAt(k) - 'A') { // i와 알파벳이 같으면
                            intalpha[i] += Math.pow(10, (word[j].length() - 1) - k);
                        }
                    }
                }
            }
        }

        Arrays.sort(intalpha);

        int k = 9;
        int sum = 0;
        for (int i = intalpha.length - 1; i >= 0; i--) {
            if (intalpha[i] == 0) break;
            intalpha[i] *= k--;
            sum += intalpha[i];
        }

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


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

결론

자릿수를 생각해내지못해 어려웠던 문제. 원소 개수가 적으니까 3중포문 돌려도된다는걸 생각하면서 푸는거랑, 그냥 푸는거랑 확실히 다른거같다.