백준 1339번 단어 수학 :: 마이구미

이번 글은 백준 알고리즘 문제 1339번 "단어 수학" 을 다뤄본다.

문제의 함정을 이해하면 백트래킹으로 접근해야한다는 것이 보인다.

하지만 본인은 수학적으로 접근하여 문제를 해결하였다.

민식이는 수학학원에서 숙제를 받았다. 숙제는 단어 수학이라는 것인데, 0-9까지의 수를 알파벳 하나로 나타낸 것이다. 그렇게 한 후, 문자가 2개 주어졌을 때, 그 두 수의 합을 최대로 만드는 것이다.

예를 들어, MCR + ACDEB를 계산한다고 할 때,

A = 9, B = 4, C = 8, D = 6, E = 5, R = 3, M = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

알파벳으로 이루어진 수가 N개 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

문제는 위와 같이 간단하다.

처음 접근한 방법으로는 주어지는 단어가 길수록 높은 수라고 생각했다.

그렇기에, 순수하게 길이순으로 정렬한 후, 맨 앞부터 높은 수를 부여했다.

그 결과, 채점 퍼센트가 올라가면서, 당연히 맞겠구나 생각했지만 틀렸다.

2
ABC
BCD

위와 같이 주어질 경우, 9를 A에 부여할지, B에 부여할지에 대한 처리가 필요하다.

혹시나 틀린 사람이 있다면, 위와 같은 반례를 들어보면 이러한 경우 때문에 틀렸을 것이라 생각한다.

사실상 위와 같은 반례가 있다면, 모든 경우를 탐색해야한다.

그렇기에 백트래킹으로 접근한다.

하지만 조금만 더 생각해보면, 단순한 수학으로 풀 수 있는 문제가 된다.

예를 들어보자.

ABC => 100A + 10B + C
BCD => 100B + 10C + D

문제는 결국 주어지는 단어들을 더한 최대값을 구해야한다.

주어지는 단어를 풀어보면 위와 같이 만들 수 있다.

그리고 두 단어를 더해보자.

ABC + BCD
100A + 110B + 10C + D

그 후, 정수를 기준으로 정렬을 하면 수들이 오름차순 or 내림차순 된다.

그 의미는 각 단어에 대한 수를 차례대로 부여해줄 수 있게 된다.

110B + 100A + 10C + D

그 결과, B = 9, A = 8, C = 7, D = 6 으로 부여할 수 있게 된다.

구현할 수 있는 방법은 다양하겠지만, 본인은 아래와 같이 구현했다.

각 단어에 해당하는 배열의 인덱스에 자릿수(1,10,100..) 을 더해나간다.

그렇다면, 배열의 각 인덱스에는 더해진 값들이 존재한다.

for (int i = 0; i < n; i++) {
    char[] array = sc.readLine().toCharArray();
    int pos = (int) Math.pow(10, array.length - 1);

    for (int j = 0; j < array.length; j++) {
        alphabet[array[j] - 'A'] += pos;
        pos /= 10;
    }

}

그 후, 더해진 값들이 있는 배열을 정렬한다.

정렬된 값에 대해 수를 차례대로 부여해주면 된다.

Arrays.sort(alphabet);

for (int i = alphabet.length - 1; i > -1; i--) {
    if (value == 0) {
        break;
    }

    ans += alphabet[i] * value--;
}

단순히, 각 단어에 해당하는 인덱스에 값들을 넣고, 정렬한 후, 수를 부여하는 것이 전부다.

전체 소스는 아래 Github URL을 참고하길 바란다.

백준 알고리즘 1339번 단어 수학 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/math/1339.java