[문제 바로가기] https://www.acmicpc.net/problem/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이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.출력
첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.
💡 문제 풀이
나의 코드가 잘못되었음을 알려주는 반례를 발견한 후 바로 해결할 수 있었다.
문제를 해결하고자 반복문을 통해 두 가지를 구하였다.
-
알파벳 길이가 최대 10이므로 10칸의 배열을 만들어 알파벳 자리에 맞게 위치 시킨다.
ex) AAABC → ['', '', '', '', '', 'A', 'A', 'A', 'B', 'C'] -
알파벳의 개수를 파악한다.
{'A' : 3, 'B' : 1, 'C' : 1}
반복문을 통해 두 가지를 구하였으면, 가장 앞자리에 위치하는 문자열부터 탐색하면서 가장 많이 나온 문자에게 높은 숫자의 우선권을 부여한다.
ex) 'AAABC', 'BBACC' → ['', '', '', '', '', 'AB', 'AB', 'AA', 'BC', 'CC'] 일 때
가장 앞자리에 위치한 문자열은 'AB'다. 그 중 가장 많은 문자열이 나온 것은 'A'이므로 'A'에 가장 큰 수 9를 먼저 부여한다.
다음 B에는 8을 부여한다.(C는 7이 된다.)
이런식으로 '알파벳 - 숫자'를 매칭한 다음, 주어진 문자열에 숫자를 대입하여 합을 구하면 된다.
반례 발견!!!
하지만, 위 방법대로 했을 때 통과하지 못하였다. 반례는 다음과 같다.
6
ABABABAB
BABABABA
ABABABAB
BABABABA
CCCCCCCA
CCCCCCBA
정답 : 533333350위와 같은 입력이 주어질 때, 가장 앞에 위치하는 알파벳은 'A', 'B', 'C'다.
그리고 가장 많이 나타난 알파벳은 'A'(14)이므로 'A'에게 9를 부여하게 될 것이다.
하지만, 가중치를 보게되면 'B'에게 높은 숫자를 부여하는 것이 더 큰 숫자를 만들 수 있다.
1 ~ 4번째 줄에서는 'A'와 'B'의 가중치를 비교할 수 없지만
5 ~ 6번째 줄을 보면 'A'는 일의 자리에서 2개 'B'는 십의자리에서 1개이기 때문이다.
따라서, 단순히 개수로 높은 숫자의 우선권을 비교하는 것이 아니라 '가중치'에 따라 우선권을 부여할 필요가 있었다.
코드는 다음과 같다.
import sys
N = int(input())
used = [False] * 10 # 숫자 사용 여부
words = [sys.stdin.readline().rstrip() for _ in range(N)] # N개의 단어를 담은 배열
alphabets = set() # 출현한 알파벳
"""N개의 문자열에서 나온 알파벳 구하기"""
for word in words:
alphabets = alphabets | set(word)
alphabets = list(alphabets)
"""
각 알파벳의 가중치 구하기 - 알파벳이 일치하면 '1', 일치하지 않으면 '0'
ex) 'ABABAA'일 때
'A'의 가중치는 101011
'B'의 가중치는 010100
"""
weight = {}
for alpha in alphabets:
for word in words:
temp = ''
for w in word:
if w == alpha: temp += '1'
else: temp += '0'
if alpha not in weight.keys(): weight[alpha] = int(temp)
else: weight[alpha] += int(temp)
weight = sorted(weight.items(), key=lambda x:[-x[1]])
"""가중치에 따라 높은 숫자 부여하기"""
result = {}
for alpha, value in weight:
for idx in range(10):
if not used[idx]:
result[alpha] = 10-idx-1
used[idx] = True
break
"""합 구하기"""
answer = 0
for word in words:
temp = ''
for alpha in word:
temp += str(result[alpha])
answer += int(temp)
print(answer)
