백준 1132 자바 - 합 (BOJ 1132 JAVA)

문제 : boj1132

 

1.

  쉽게 생각할 수 있는 방식인 단순히 자리수가 높다고 높은 수를 주는 방식은 쉽게 반례를 찾을 수 있다.

AB

B

B

B

B

B

B

B

B

B

B

와 같은 입력에 대해 단순히 A가 자리수가 크다고 9를 주면 안된다. B가 11개인 위와 같은 경우 B를 9를 줘야 최대값이 나온다.

 

 

2.

  이런 경우 자리수에 따른 가중치를 계산해야 한다. 1위 자리에 나온 수라면 +1의 가중치, 10의 자리라면 +10, ... 와 같은 방식이다. 예를들어 '예제 입력 1'에 나온 각 문자는 다음과 같이 가중치를 구할 수 있다.

  

  그럼 가중치가 높은 순서대로 더 높은 수를 주면 된다(그리디). 따라서 B=9, A=8, C=7이 된다.

 

 

3.

  만약 A~J가 아니라, A~I 까지 였다면 9~1을 주면 되니까 쉬웠는데, 이 문제의 경우 '0으로 시작하는 수는 없다.' 라는 조건이 있다. 이 부분때문에 구현이 상당히 빡쌔진다 ㅋㅋ 위 제한을 문제에 적용시키면 각 문자에서 가장 왼쪽에 나왔던 문자는 0이 될 수 없다. 

 

  예제 입력 4를 보자. 가중치 순서대로 정렬해보면 A > J=I > H > G > F > E > D > C > B 이다. 근데 여기서 가장 좌측에 나왔던 A~I는 0이 될 수 없으니 가중치가 크더라도 J가 0이 되어야만 한다. 

  이걸 해결하려면 어떻게 해야할지 보자.

 

A. 일단 A~J까지 모든 문자가 한번이라도 나왔는지 확인해야 한다. 만약 A~I까지만 등장했다면 애초에 9~1까지만 매칭하면 되므로 0을 생각하지 않아도 된다.

 

B. A~J까지 모든 문자가 등장한적이 있으면서 가중치가 가장 낮은 항목이 0이 되면 안되는 경우 (위의 경우 모든 문자가 나왔고, 가중치가 가장 낮은 B는 0이 될 수 없다.) -> 가중치가 낮은 순서대로 확인하며, 0으로 가능한 경우를 찾는다. 위의 예시에서는 J가 가능하다.

 

C. 찾았다면 해당지점부터 한칸씩 앞으로 땡겨주고, 마지막에 0이 가능한 수를 넣으면 된다.

 

D. 이제 이 순서대로 9~0을 매칭시켜주면 된다.

 

 

코드 : github

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

interface Tags {
    public static final int LEN_OF_A_TO_J = 'J'-'A'+1;
}

class Alphabet implements Comparable<Alphabet> {
    static boolean[] exist = new boolean[Tags.LEN_OF_A_TO_J];
    static int cnt = 0;

    int idx;
    long weight;
    boolean notZero;

    public Alphabet(int idx) {
        this.idx = idx;
        this.weight = 0;
        this.notZero = false;
    }

    public void addWeight(long weight) {
        this.weight += weight;
        setExist();
    }

    private void setExist() {
        if (!exist[idx]) {
            cnt++;
            exist[idx] = true;
        }
    }

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Alphabet[] alphabets = new Alphabet[Tags.LEN_OF_A_TO_J];
        for (int i = 0; i < alphabets.length; i++) {
            alphabets[i] = new Alphabet(i);
        }
        String[] arr = new String[n];

        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            arr[i] = s;

            long w = 1;
            for (int j = s.length()-1; j >= 0; j--, w*=10) {
                int idx = s.charAt(j) - 'A';
                alphabets[idx].addWeight(w);
                if (j==0) {
                    alphabets[idx].notZero = true;
                }
            }
        }

        Arrays.sort(alphabets);
        if (Alphabet.cnt == Tags.LEN_OF_A_TO_J && alphabets[alphabets.length-1].notZero) {
            for (int i = alphabets.length-2; i >= 0; i--) {
                if (!alphabets[i].notZero) {
                    Alphabet tmp = alphabets[i];
                    for (int j = i; j < alphabets.length-1; j++) {
                        alphabets[j] = alphabets[j + 1];
                    }
                    alphabets[alphabets.length-1] = tmp;
                    break;
                }
            }
        }

        int[] weight = new int[Tags.LEN_OF_A_TO_J];
        int digit = 9;
        for (Alphabet ap : alphabets) {
            weight[ap.idx] = digit--;
        }

        long sum = 0;
        for (String s : arr) {
            long cur = 0;
            long w = 1;
            for (int j = s.length()-1; j >= 0; j--, w*=10) {
                int idx = s.charAt(j) - 'A';
                cur += weight[idx]*w;
            }
            sum += cur;
        }
        System.out.println(sum);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}