백준 1132번 - 합

문제

백준 1132번 - 합

아이디어

자릿수의 합이 가장 큰 알파벳에 최대한 큰 수를 배치하는 것이 큰 수를 만들기에 유리하다. 예를 들어 예제 1의 경우는 A=101, B=110, C=11 이므로 B, A, C 순으로 큰 수를 배치한다.

코드 구현 - 자바

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

public class BJ_1132 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        long[][] alphas = new long[10][2];

        // 1
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            alphas[s.charAt(0) - 'A'][0] = 1;   //첫 문자

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

        // 2
        Arrays.sort(alphas, Comparator.comparingLong(a -> a[1]));

        boolean[] used = new boolean[10];
        long ans = 0;

        // 3
        for (long[] alpha : alphas) {
            for (int j = (int) alpha[0]; j < 10; j++) {
                if (!used[j]) {
                    used[j] = true;
                    ans += alpha[1] * (long) j;
                    break;
                }
            }
        }

        System.out.println(ans);
    }
}

1

• alphas 배열은 A부터 J까지 최대 10개 알파벳의 자릿수의 합과 첫 문자 여부를 저장한다.
• 첫 문자는 수가 0으로 시작할 수 없어야 한다. 이 알파벳은 최소 1부터 수가 배치될 수 있다.

2

• 자릿수의 합을 기준으로 정렬한다.

3

• alpha[0]은 0 또는 1이 담겨있다. 해당 알파벳이 첫 문자이면 1부터 배치되고, 그렇지 않으면 0이 배치될 수 있다.
• 배열은 자릿수의 합이 작은 알파벳부터 탐색되므로 작은 수부터 배치하여 큰 자릿수에는 큰 수가 배치될 수 있도록 한다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)