[백준] 1339번 단어 수학

1) 생각

문자가 주어지면 각 문자들을 숫자로 바꾸어서 가장 큰 숫자를 만들어야한다. 분류에는 백트래킹으로 되어있는걸로 봐서는 바꿔가면서 해보라는 뜻이겠지만 다른 방법을 사용하여 간단히는 아니지만(오류가 있었다..) 간단히 풀었다.

예제를 살펴보면 다음과 같다.

입력      출력
2          1998
AAA
AAA

가장 큰 수를 만드려면 가장 큰 자리수를 큰 숫자로 만들어야한다. 따라서 위의 예제의 경우 A가 9가 되어야한다. 하지만 다음과 같다면 어떨까

입력      출력
2          1878
BCA
AAA

B와 A중에 A가 9의 값을 가져야 더 큰값이 된다는 것을 알 수 있지만 자리수로만 따져 B가 9 가되면 가장 큰 숫자가 되지 못한다. 따라서 가중치를 모아서 가장 큰 가중치를 가진 문자가 9부터 차례대로 값을 가져야한다.

2번째의 경우 B는 100이라는 가중치를 가지고 있다. C는 10, A는 1을 가지고 있다.

두번째를 조사하면 B는 그대로 100 C는 그대로 10, A는 100+10+1 을 더하여 112의 가중치를 가지게 된다. 이런식으로 조사를 하여 가중치에 따라 높은 숫자를 주면 답을 얻을 수 있다.

이러한 방법으로 코드를 작성하였지만... 'Runtime Error'를 맞이했고 30분동안 뚫어지게 쳐다본 결과 오류 이유를 찾아낼 수 있었다.

2) 방안

문제에서 다음과같은 문장이 주어진다.

입력

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다

여기서 '알파벳은 최대 10개'에 사로잡혔다. 예제에도 10개로 주어지는 Case에서 A~I 까지 주기 때문에 사로잡혔었다.

알파벳을 담을 배열의 크기를 10개에서 26개로 늘려주었더니 문제를 해결했다. 주어진 단서들을 폭넓게 봐야지 정확히 판단하고 풀 수 있다는걸 다시금 깨닫게해준 고마운? 문제다.

import java.util.Arrays;
import java.util.Scanner;
 
public class Main{
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        String[] arr = new String[n];
        for(int i=0;i<n;i++)
            arr[i] = sc.next();
        // A(0) ~ J(9) 까지 => A~Z까지!
        int[] num = new int[26];
        for(int i=0;i<n;i++) {
            String t = arr[i];
            for(int j=0;j<t.length();j++) {
                num[(t.charAt(j)-65)] += (int)Math.pow(10,(t.length()-j-1));
            }
        }
        Arrays.sort(num);
        int result = 0;
        for(int i=25,k=9;i>=0;i--,k--) {
            if(num[i]==0) break;
            result += (num[i]*k);
        }
        System.out.println(result);
    }
}