백준 1339 자바 - 단어 수학 (BOJ 1339 JAVA)

문제 : boj1339

 

1. 그리디 문제이다.

  대충봐도 어떠한 문자를 9~0 중 어떤걸 선택해야 하는지 파악해야 하는 문제이므로 그리디 문제임을 알 수 있다. 이 때, 단순히 자리수가 높다고 높은 수를 줘버리면 다음과 같은 반례를 통과할 수 없다. A가 가장 자리수가 높으므로 9를 주고, Z를 8을 주면 총 합은 1780이 된다. 하지만 A를 8, Z를 9로 하면 1790이 나오므로 Z를 9로 주는 것이 이득임을 알 수 있다.

10
AZZ
ZZ
ZZ
ZZ
ZZ
ZZ
ZZ
ZZ
ZZ
ZZ

 

 

2. 해결 방법

  각 자리수에 대해 가중치를 주는 방식으로 해결할 수 있다. 즉, 1의 자리에 나온 문자는 가중치 1, 10의 자리는 10, ... 이런식이다. 예를들어 '예제 입력 2'는 다음과 같이 표현할 수 있다.

 

[GCF] G=100, C=10, F=1

[ACDEB] A=10000, C=1000, D=100, E=10, B=1

 

N개의 입력으로 들어온 문자에 대해 위와 같은 방식으로 가중치를 구한다면, 각 알파벳 별로 총합이 끼치는 가중치를 알 수 있다. 위의 경우 다음과 같을 것이다. 즉, 입력으로 들어온 N개의 가중치를 모두 합쳐서, A~Z의 모든 문자열의 가중치를 구하는 것이다.

 

  입력이 다음과 같을 때의 가중치도 예시로 첨부한다.

4
ABC
BBB
CA
ABAA

 

  그럼 이렇게 각 문자별 가중치가 구해진다면, 가중치 내림차순으로 정렬 후 전체 합에 끼치는 가중치(영향)이 큰 문자부터 높은 숫자로 변경하면 된다. 예제 입력 2 (GCF, ACDEB)의 경우엔 그럼 A=9, C=8, D=7(또는 G=7), G=6(또는 D=6), E=5, B=4(또는 F=4), F=3(또는 B=3) 과 같다. 가중치가 동일할 경우엔 뭘 먼저 줘도 상관없다.

 

  0으로 시작하는 2자리 이상의 수(AC라는 입력이 있고, A가 0이 된 경우와 같이)가 반례가 될까 걱정했는데, 딱히 문제에 써있지도 않고 따로 처리안하고 틀리면 처리해볼 생각이었는데 통과되는걸로 보아 별 상관없는 듯 하다. 별 문제 없이 통과됬다.

 

 

3. 추가 추천 문제

  1036번 36진수를 추천한다. 비슷한 논리로 풀 수 있는데, 훨씬 구현이 까다로워서 더 재밌다. 나만 당할순없지

 

 

 

코드 : github

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

class Weight {
    char c;
    int w;
    public Weight(char c, int w) {
        this.c = c;
        this.w = w;
    }
}
public class Main {
    private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        String[] arr = new String[n];

        Weight[] weight = new Weight['Z'-'A'+1];
        for (int i = 0; i < weight.length; i++) {
            weight[i] = new Weight((char)('A'+i), 0);
        }
        for (int i = 0; i < n; i++) {
            String cur = br.readLine();
            arr[i] = cur;
            for (int j = 0; j < cur.length(); j++) {
                weight[cur.charAt(j)-'A'].w += Math.pow(10, cur.length()-j-1);
            }
        }

        Arrays.sort(weight, new Comparator<Weight>() {
            @Override
            public int compare(Weight o1, Weight o2) {
                return o2.w - o1.w;
            }
        });

        int[] atoi = new int['Z'-'A'+1];
        int num = 9;
        for (Weight cur : weight)
            atoi[cur.c-'A'] = num--;

        int answer = 0;
        for (String str : arr) {
            for (int j = 0; j < str.length(); j++) {
                answer += atoi[str.charAt(j)-'A']*Math.pow(10, str.length()-j-1);
            }
        }
        System.out.println(answer);
    }

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