[백준] 1132번 합(java)

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

1132번: 합

전에 풀었던 문제에서 조건이 하나 추가되었다.

 

 

핵심 

위의 문제는 만약 ABC + DAB 라면 100A + 10B +C + 100D+ 10A+B로 둘 수 있다.

이를 110A + 100D +11B  +C로 둘 수 있다. 따라서 A에 가장 큰 9, D에 8B에 7C에 6을 넣어주면 된다.

단 새로운 조건이 추가되었다. 맨 앞자리가 0이 되면 안 된다.

위의 경우에는 해당되지 않지만, 수가 많아지면 0의 조건이 필요해진다.

 

 

 

정답 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Alpha[] alphas = new Alpha[10];
        for (int i = 0; i < 10; i++) {
            alphas[i] = new Alpha();
        }

        for (int i = 0; i < n; i++){
            String str = sc.next();
            alphas[str.charAt(0)-'A'].num += Math.pow(10, str.length() -1);
            alphas[str.charAt(0)-'A'].first = true;
            for (int j = 1; j < str.length(); j++){
                alphas[str.charAt(j) - 'A'].num += Math.pow(10,str.length()-j-1);
            }
        }

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

        Arrays.sort(alphas);



        for (int i = 0 ; i < 10; i++){
            if (alphas[i].first){
                for (int j = 1; j<=9; j++){
                    if (!used[j]){
                        used[j] = true;
                        sum += alphas[i].num * (long)j;
                        break;
                    }
                }
            }else {
                for (int j = 0; j<=9; j++){
                    if (!used[j]){
                        used[j] = true;
                        sum += alphas[i].num * (long)j;
                        break;
                    }
                }
            }
        }

        System.out.println(sum);

    }
}

class Alpha implements Comparable<Alpha>{
    long num = 0;
    boolean first = false;

    @Override
    public int compareTo(Alpha o) {
        if(num>o.num)return 1;
        if(num==o.num)return 0;
        else return -1;
    }
}

해설

Alpha라는 클래스를 만든다. 각각은 A, B, C... J를 의미한다.

또한 첫자리에 나타나는 알파벳의 경우 first가 true값을 갖게 된다.

이제 입력값을 분해해서 각각의 알파벳에 대입해 준다.

이후 작은 순으로 정렬한 뒤, 작은 값부터 1개씩 넣어준다.

작은 값부터 넣어주고, 이미 넣은 값은 무시하게 된다.

 

 

 

배운 점

Alpha클래스에서 compareTo 부분을 return this.num - o.num으로 두었더니 오류가 터졌다.

이유는 빼는 과정에서 오버플로우가 발생하여 우리가 원하는 대로 작동하지 않았던 것이다.

long타입의 경우 위 코드처럼 직접 리턴값을 설정해주어야 한다.