https://www.acmicpc.net/problem/1339
1339호: 단어 수학
단어 수 N(1 ≤ N ≤ 10)은 첫 번째 줄에 표시됩니다. 두 번째 줄부터 N 줄에 한 줄에 한 단어가 주어집니다. 단어는 대문자로만 구성됩니다. 모든 단어에 포함된 알파벳은 최대
www.acmicpc.net
문제 해결
이 문제를 보고 바로 떠오른 알고리즘 과정은 다음과 같다.
1. 입력 값 중 가장 긴 문자열 찾기
2. 알파벳으로 입력할 수 있는 숫자 중 가장 큰 숫자를 처음부터 순서대로 지정
3. 최대 길이가 8이므로 나머지 숫자는 순서대로 부여
4. 알파벳 숫자를 대입하여 합산
그리고 어떻게 숫자를 추출할지 고민하다가 queue 데이터 구조를 이용해서 가장 큰 숫자부터 먼저 출력하면 좋겠다는 생각이 들었습니다.
위의 알고리즘으로 문제를 풀다가 문제를 발견했습니다. 일의 자리는 백의 자리보다 클 필요가 없습니다. 그래서 아래와 같이 알고리즘을 수정했습니다.
1. 문자열 길이가 가장 긴 문자부터 순차적으로 숫자 지정
2. 다음으로 긴 문자열의 길이를 순서대로 번갈아 지정하십시오.
접근은 좋았지만 결국 이 문제는 스스로 해결하지 못했다 기타나는 해결책을 보았다
import sys
n = int(sys.stdin.readline())
alpha = ()
alpha_dict = {}
numList = ()
for i in range(n):
alpha.append(sys.stdin.readline().rstrip())
for i in range(n):
for j in range(len(alpha(i))):
if alpha(i)(j) in alpha_dict:
alpha_dict(alpha(i)(j)) += 10 ** (len(alpha(i))-j-1)
else:
alpha_dict(alpha(i)(j)) = 10 ** (len(alpha(i))-j-1)
for val in alpha_dict.values():
numList.append(val)
numList.sort(reverse=True)
sum=0
pows=9
for i in numList:
sum += pows * i
pows -= 1
print(sum)이 코드의 핵심은 다음 코드입니다.
if alpha(i)(j) in alpha_dict:
alpha_dict(alpha(i)(j)) += 10 ** (len(alpha(i))-j-1)
else:
alpha_dict(alpha(i)(j)) = 10 ** (len(alpha(i))-j-1)알파벳이라는 단어가 이미 사전에 있으면 원래 값에 추가하고, 없으면 사전에 새로 추가하는 코드입니다. 그 이유는 다음과 같습니다.
pows = 9
for i in numList:
sum += pows * i
pows -= 1입력값이 aaa, abc이면 사전은 {‘a’: 211, ‘b’: 10, ‘c’: 1}을 이렇게 저장한다. a가 211인 이유는 100번째 자리에 a가 10번째 자리에 한 번, 1번째 자리에 한 번, 두 번 나타나기 때문입니다. a의 값이 가장 큰 부분을 차지하므로 9부터 순서대로 곱하면 답을 구할 수 있다.
이 문제를 해결하는 포인트는 각 숫자에 알파벳이 나타나는 횟수를 저장해 두었다가 그 숫자를 9부터 순차적으로 곱해서 더하는 것이다. 이런 생각을 한 번에 바꿀 생각을 못해서 안타깝고, 이제 이런 식으로 해결될 수 있다는 걸 알았으니, 이런 식으로 적용해서 해결해야 할 문제가 있다면 적용해봐야겠네요. 그것을 해결하십시오.