(알고리즘) 백준 1132 java 자바

문제

백준 1132 합 : https://www.acmicpc.net/problem/1132

N개의 수가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으로 시작하는 수는 없다. 이때, 가능한 수의 합 중 최댓값을 구해보자.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 수가 주어진다. 수의 길이는 최대 12이다. 적어도 한 알파벳은 수의 가장 처음에 주어지지 않는다.

출력

첫째 줄에 합의 최댓값을 출력한다.

예제 입력 1

2
ABC
BCA

예제 출력 1

1875

예제 입력 2

1
ABCDEFGHIJ

예제 출력 2

9876543210

예제 입력 3

2
ABCDEFGHIJ
J

예제 출력 3

9876543202

예제 입력 4

10
A
BB
CCC
DDDD
EEEEE
FFFFFF
GGGGGGG
HHHHHHHH
IIIIIIIII
AJJJJJJJJJ

예제 출력 4

9973936905

예제 입력 5

5
GHJIDDD
AHHCCCA
IIJCEJ
F
HDBIGFJAAJ

예제 출력 5

9888114550

풀이

풀이는 어렵지 않다. 0~9까지의 A~J에 해당하는 배열을 만들어준다.
그 이후 ABB에서 A의 경우 100 B의 경우 10+1이 될 수 있도록, 각 자리에 해당하는 10의 거듭제곱을 각 배열에 더해준다
예로서 ABC와 CBA가 있을 경우 A는 100+1 B는 10+10 C의 경우 1+100이 되면 된다. 이때 각 자리의 첫 자리수의 경우 절대로 0이 될 수 없다. 이를 체크하기 위한 클래스를 만들고 여기에 첫자리인지 아닌지와 함께 수를 더해준다.
이후 해당 배열을 정렬 한 뒤 0부터 곱해가는데 이때 넣어야 하는 알파벳이 처음으로 나온 경우가 있을 경우 아직까지 1 이후부터 사용하지 않은 수 순서대로 넣어준다. 자세한 내용은 코드가 더 쉬울 것이다.

코드

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

public class Boj1132
{
    static class Info implements Comparable<Info> {
        long num=0;
        boolean first=false;


        @Override
        public int compareTo(Info o) {
            if(num>o.num){
                return 1;
            }
            if(num==o.num){
                return 0;
            }
            else
            {
                return -1;
            }
        }//단순하게 빼버렸다가 오버플로우 문제가 발생했다. java에서 오버플로우 조심하도록 하자
    }
    static public void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(bf.readLine());
        Info cal[]=new Info[10];
        for(int i=0;i<10;i++){
            cal[i]=new Info();
        }
        for(int t=0;t<n;t++) {
            String s1 = bf.readLine();
            cal[(int) (s1.charAt(0) - 'A')].num += Math.pow(10, s1.length() - 1 - 0);
            cal[(int) (s1.charAt(0) - 'A')].first=true;//맨 처음 나온 수의 경우 처음 나왔다고 표시해둔다
            for (int i = 1; i < s1.length(); i++) {
                cal[(int) (s1.charAt(i) - 'A')].num += Math.pow(10, s1.length() - 1 - i);//각 자리의 수에 해당하는 10의 거듭제곱을 더해준다
            }
        }
        long ans=0;
        Arrays.sort(cal);//정렬한뒤
        int used[]=new int[10];

        for(int i=0;i<10;i++){
            if(cal[i].first){//만약 첫번째 자리 수 였을 경우
                for(int j=1;j<10;j++){//1이상의 수 중 가장 작은 수를 곱해서 더해준다.
                    if(used[j]==0){
                        ans+=cal[i].num*(long)j;
                        used[j]=1;
                        break;
                    }
                }
            }
            else {
                for(int j=0;j<10;j++){
                    if(used[j]==0){//첫자리가 아닐 경우 가장 작은 수를 더해준다.
                        ans+=cal[i].num*(long)j;
                        used[j]=1;
                        break;
                    }
                }
            }
        }
        System.out.println(ans);

    }
}

후기

문제는 어렵지 않았으나 long오버플로로 인해 시간이 오래 걸렸던 문제. java에서 처음으로 long을 사용해 보았다. 이제 long으로 인한 문제는 겪어 보았으니 앞으로는 안겪어야지. 조금은 발전한듯!