[골드 4] 1339번: 단어 수학

Original Source: https://www.acmicpc.net/problem/1339

1339번: 단어 수학

---

문제

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

---

사고의 흐름

• 알파벳과 숫자를 대응시키는 모든 경우의 수를 구현하는 게 관건이겠군.
• 숫자 집합을 (0, 1, ..., 9) 로 하나 만들고, 알파벳 집합도 만든 다음 둘 사이의 대응 관계를 계속 변화시키면 되겠는데.
• '모든 대응 관계'면 순열, 즉 팩토리얼인데, 팩토리얼을 어떻게 구현하지?
• 이코테 강의에서 itertools 라이브러리를 사용하면 모든 경우를 쉽게 찾을 수 있다고 하던데, 어떻게 사용하는지 알아봐야겠다.
• permutations() 메서드를 사용하면 되겠네. 그럼 숫자 리스트를 만든 다음 permutations() 메서드를 써서 가능한 모든 경우의 숫자 리스트들을 만들어 놓고, 알파벳을 거기에 대응시키는 게 낫겠다. 왜냐하면 알파벳은 각 Input별로 변동이 일어나지만, 숫자는 0 ~ 9까지 고정이니까, 고정된 숫자 리스트를 변화시키는 편이 조금이라도 덜 복잡한 코드를 작성하는 데 좋을 테니까.
• 위처럼 하지 말고 숫자 리스트, 알파벳 리스트를 각각 만든 다음 product() 메서드를 사용하면 모든 대응의 경우를 더 간편하게 얻을 수 있겠다.
• 생각 외로 메서드들이 시간을 많이 잡아먹는데? 하긴 10! = 3628800 의 경우를 모두 출력했으니 그렇지. 출력하지 않고 계산만 한 다음 그 중 일부만 출력하면 괜찮지 않을까?
• 최적화는 나중에 생각하고 우선 '동작하는 코드'부터 작성하자.

 

• product() 메서드는 두 리스트 중 각각 하나의 원소를 '선택'해서 짝지어줄 뿐, 모든 대응을 자동으로 리턴하지 않는다. 쉽지 않네...
• 그럼 결국 이 product() 메서드나 뭐가 됐던 간에 다른 메서드를 매우 많이 반복해서 사용해야 한다는 소리인데, 그러면 무조건 시간 초과가 날 것 같다. 이 문제는 완전 탐색이 아니라 그리디다. 해답을 구하는 방법을 따로 찾아야 한다.
• 확실해 보이는 사실은 길이가 가장 긴 단어의 앞자리부터 가장 큰 숫자들을 할당해야 한다. 문제는 길이가 동일한 문자열을 계산할 때다.
• 우선 길이가 동일한 두 문자열 사이에 공통된 문자가 없다면, 각 문자가 어떤 숫자에 할당되는지에 상관없이 남은 숫자들 중 가장 큰 숫자부터 0까지 두 문자열의 앞쪽부터 차례로 할당해주면 된다.
• 만약 공통된 문자가 있다면? 이 경우는 앞에서 어떤 문자에 어떤 숫자를 할당하냐에 따라 합이 변한다.

 

• 나는 길이가 가장 긴 문자열에 대응되는 숫자를 가장 크게 만들어주면 된다고 생각했다. 예를 들어 Input이 2 / GCF / ACDEB 라면 ACDEB = 98765, GCF = 483 과 같이 대응하면 된다고 생각했는데, 그게 아니다. 말하자면 가로가 아니라 세로로 비교해야 한다. 우선 AC = 98 로 대응한 다음, 나머지 문자들 즉 G8F / DEB 를 놓고 각 경우를 따져 가며 비교해야 한다.
• 위 Input에서 가능한 후보군은 [784 / 653], [783 / 654], [684 / 753], [683 / 754] 다. 그렇다면 두 문자열의 길이가 다르다고 해도 '각 문자가 어떤 숫자에 할당되는지에 상관없이 남은 숫자들 중 가장 큰 숫자부터 0까지 두 문자열의 앞쪽부터 차례로 할당해야' 한다.
• 이제 공통된 문자가 있는 경우만 해결하면 된다.

 

• 지금까지의 접근 방식은 틀렸다. 극단적인 반례로 10 / ACC / CC / CC / CC / ... / CC 와 같은 Input을 생각해보자. 이 경우 단순히 A가 가장 앞에 있다고 해서 A에 9를 할당하면 안 된다. 왜냐하면 C = 9, A = 8인 경우 합이 더 크기 때문이다.
• 이 문제의 해법은 문자열의 각 문자를 카운팅하되 문자의 위치별로 가중치를 두는 것이다. 예를 들어 'AOO'의 A는 'A'가 100 == 10^2개 있는 것과 같다. 즉 위치별로 10^(위치)의 가중치를 두어 문자를 카운팅해 문자열을 변환하는 함수를 만든 다음, 개수가 가장 많이 나온 문자부터 높은 숫자를 부여해 계산하면 된다. 수의 최대 길이가 8이므로 8개의 위치만 고려하면 된다.
• 문자를 카운팅한 뒤 결과를 반환할 필요 없이 바로 정렬한 다음 합을 계산해도 된다. 어차피 문자가 뭐든 간에 빈도가 높은 문자부터 높은 숫자를 할당하면 되니까. 

내가 작성한 소스코드

import sys

def count_chars(li):
    chs = dict()

    for v in li:
        for i in range(len(v)):
            if v[i] not in chs.keys():
                chs[v[i]] = 0

            chs[v[i]] += 10 ** (len(v) - (i+1))

    chs = dict(sorted(chs.items(), key=lambda item: item[1], reverse=True))
    
    return chs


n = sys.stdin.readline().rstrip()
inputs = []
for line in sys.stdin:
    inputs.append(list(line.rstrip()))

chars = count_chars(inputs)
keys = list(chars)

answer = 0
for i in range(len(keys)):
    answer += chars[keys[i]] * (9-i)

print(answer)

피드백

• 대응 문제 ⇒ 순열/조합 이 아니다. 두 집단 사이의 모든 관계를 생각해야 한다고 해서 무조건 순열, 조합을 사용할 것이라 예측하지 말자.
• 자릿수를 파악해야 하는 문제에서 '가중치' 개념이 유용하게 사용되는 것 같다. 대표적으로 이진법 ↔ 십진법 변환 문제가 있다. 자릿수 문제가 나오면 우선 '각 자리별로 숫자의 진법에 해당하는 가중치를 부여할 수 있다' 는 사실을 상기시키자.