아이디어

• 높은 자리에서 가장 많이 나오는 순서대로 9, 8, 7, …등을 할당한다.
• 어떤 자릿수에 대해 나온 횟수가 동일하다면 다음으로 작은 자릿수를 비교하고, 우열이 결정될 때까지 반복한다.
  • 1의 자리에서도 결정이 안 난다면 그 둘 사이에는 어찌되도 상관 없다.
• 각 문자가 등장할 때마다 그 문자의 자릿수 가중치($10^k$)를 누적한 값이 높으면 높은 숫자를 할당한다.
• 그렇게 한 결과 ‘0’으로 시작한 문자열이 있다면 현재 일의 자리를 다음 자리와 바꾸고, 그래도 안 되면 더 높은 자리로 바꾸고… 등을 반복한다.
• 각 자릿수와 0~9까지에 대해 (그 숫자에 해당하는 문자가 그 자리에 나온 횟수 문자에 해당하는 숫자값 자릿수에 대한 가중치)의 합을 구하면 답이 될 것이다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));

    static int N;
    static char[][] strs;
    static long[] weights = new long['J'+1];
    static long[] pow10 = new long[12];
    static int[] values = new int['J'+1];

    public static void main(String[] args) throws Exception {
        // init: 10의 제곱수들을 저장해놓는다.
        pow10[0] = 1L;
        for (int i=1; i<12; i++) pow10[i] = pow10[i-1] * 10L;

        // N개의 수를 입력받아 각 문자열을 저장하고 각 자릿수에 나오는 횟수를 카운트한다.
        N = Integer.parseInt(rd.readLine());
        strs = new char[N][];
        for (int i=0; i<N; i++) {
            char[] s = rd.readLine().trim().toCharArray();
            strs[i] = s;
            for (int j=0; j<s.length; j++) {
                weights[s[s.length-1-j]] += pow10[j];
            }
        }

        // A~J를 12번째 자릿수부터 카운트 순서대로 정렬한다. 같으면 그 아래 자릿수를 대상으로 계속 비교
        // 정렬결과 chs[i]는 숫자 i를 나타내는 알파벳이 된다. (후처리 제외)
        Character[] chs = new Character[] {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
        Arrays.sort(chs, (a, b) -> weights[a] < weights[b] ? -1 : 1);

        // 만약 첫 자리가 chs[0]인 문자열은 0으로 시작하는 문자열이 있다는 뜻이므로
        // 어쩔 수 없이 chs[0]를 더 큰 자리 수와 바꿔야 한다.
        // 모든 문자열이 0으로 시작하지 않을 때까지 바꿀 자릿수를 늘리며 반복한다.
        boolean zeroLead = true;
        int idx = 1;
        while (zeroLead) {
            for (int i = 0; i < N; i++) {
                zeroLead = (strs[i][0] == chs[0]);
                if (zeroLead) {
                    Character tmp = chs[0];
                    chs[0] = chs[idx];
                    chs[idx] = tmp;
                    idx++;
                    break;
                }
            }
        }

        // 각 알파벳이 가지는 값, 즉 chs[i]의 역방향 참조
        for (int i=0; i<10; i++) {
            values[chs[i]] = i;
        }

        // 각 자릿수의 알파벳에 수를 대입해 합을 구해준다.
        long sum = 0;
        for (int i=0; i<N; i++) {
            int len = strs[i].length;
            for (int j=0; j<len; j++) {
                sum += values[strs[i][len-1-j]] * pow10[j];
            }
        }

        System.out.println(sum);
    }
}

메모리 및 시간

• 메모리: 14340 KB
• 시간: 132 ms

리뷰

• 중간에 아이디어를 수정했는데, 카운트를 문자와 자릿수에 대한 2차원 배열로 세는 것은 반례가 있다.

  11
  AB
  B
  B
  B
  B
  B
  B
  B
  B
  B
  B

  • 여기서 위 취소선의 방식대로 하면 (cnts[’A’][1], cnts[’A’][0])와 (cnts[’B’][1], cnts[’B’][0])가 (1, 0), (0, 11)이 되어서 A가 우선이 되는데, 실제로는 (A, B) = (9, 8)일 때 지분이 각각 90, 88로 합이 178인 것보다 (A, B) = (8, 9)일 때 지분이 각각 80, 99로 합이 179로 더 커지므로 B가 우선이 되어야 한다.
• 그리디 알고리즘 문제를 풀 때는 데이터의 우선순위를 결정할 키 값이 무엇인지를 잘 따져보는 게 중요한 것 같다.
• 난이도로 문제의 복잡성을 가늠하는 습관은 좋지 않지만, 문제의 예상 난이도보다 복잡한 방법은 정답이 아닐 가능성이 높다는 걸 명심하자.
  • 이전 아이디어를 구현하려면 Comparator에 재귀함수까지 들어갔기 때문에…
• 가급적 STL 말고 merge sort 정도는 바로바로 구현할 수 있게 익혀두자! (B형에서 라이브러리가 풀렸다 해도)

이전 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));

    static int N;
    static char[][] strs;
    static int[][] cnts = new int['J'+1][12];
    static long[] pow10 = new long[12];

    public static void main(String[] args) throws Exception {
        // init: 10의 제곱수들을 저장해놓는다.
        pow10[0] = 1L;
        for (int i=1; i<12; i++) pow10[i] = pow10[i-1] * 10L;

        // N개의 수를 입력받아 각 문자열을 저장하고 문자가 등장한 자릿수의 가중치를 누적한다.
        N = Integer.parseInt(rd.readLine());
        strs = new char[N][];
        for (int i=0; i<N; i++) {
            char[] s = rd.readLine().trim().toCharArray();
            strs[i] = s;
            for (int j=0; j<s.length; j++) {
                cnts[s[j]][s.length-1-j]++;
            }
        }

        // A~J를 12번째 자릿수부터 카운트 순서대로 정렬한다. 같으면 그 아래 자릿수를 대상으로 계속 비교
        // 정렬결과 chs[i]는 숫자 i를 나타내는 알파벳이 된다. (후처리 제외)
        Character[] chs = new Character[] {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
        Arrays.sort(chs, new Comparator<Character>() {
            @Override
            public int compare(Character a, Character b) {
                return compareWeight(a, b, 11);
            }

            int compareWeight(char a, char b, int weight) {
                if (weight == -1)
                    return 0;
                int result = cnts[a][weight] - cnts[b][weight];
                if (result == 0)
                    return compareWeight(a, b, weight-1);
                return result;
            }
        });

        // 만약 첫 자리가 chs[0]인 문자열은 0으로 시작하는 문자열이 있다는 뜻이므로
        // 어쩔 수 없이 chs[0]를 더 큰 자리 수와 바꿔야 한다.
        // 모든 문자열이 0으로 시작하지 않을 때까지 바꿀 자릿수를 늘리며 반복한다.
        boolean zeroLead = true;
        int idx = 1;
        while (zeroLead) {
            for (int i = 0; i < N; i++) {
                zeroLead = (strs[i][0] == chs[0]);
                if (zeroLead) {
                    Character tmp = chs[0];
                    chs[0] = chs[idx];
                    chs[idx] = tmp;
                    idx++;
                    break;
                }
            }
        }

        // 각 자릿수의 알파벳에 수를 대입해 합을 구해준다.
        long sum = 0;
        for (int i=0; i<12; i++) {
            for (int j=9; j>=0; j--) {
                sum += cnts[chs[j]][i] * j * pow10[i];
            }
        }

        System.out.println(sum);
    }
}