백준 1339 단어 수학

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/1339

풀이

난이도 : Gold IV

이 문제는 주어진 알파벳을 숫자로 치환하여 가장 큰 숫자들의 덧셈의 결과를 찾는 문제이다.
입력으로 주어지는 단어의 개수 N은 1이상 10이하이고, 문자들의 최대 길이는 8이므로 시간초과에 대한 걱정은 하지 않았다.

1. 처음에는 AAAAA + BBBB 같은 문자열이 있을 때 A를 9로 두고, B를 8로 두면 99999 + 8888로 가장 큰 값이 나올 것이라 예상하여 가장 자릿수가 높게 보이는 문자부터 정렬하여 높은 숫자를 부여해주는 방법을 생각했다.

2. 하지만, AAA + BB + BB + BB + BB + BB + BB + BB + BB + BB + BB 과 같이 예외의 상황이 있어 문제가 발생하였다.

3. 그래서 가장 큰 자릿수만 기록하는 것이 아니라 자릿수에 해당하는 값, 즉 10의 n-1제곱 꼴의 값을 더해주는 방법으로 입력되는 문자들의 크기를 모두 기록하였다.

   👉 예) ABCA -> Apow(10, 3) + Bpow(10, 2) + Cpow(10, 1) + Apow(10, 0) 꼴로 나누어서 생각해보는 방법이다.

✔ 위의 방법으로 문자열들이 배정되는 크기를 모두 기록하고, dictionary 자료형으로 표현한 후 입력된 문자열들을 치환해 계산하여 문제 풀이를 완료하였다.

코드

n = int(input())

strings = []
array = []
d = [0] * 26

for _ in range(n):
    st = str(input())
    strings.append(st)

    for i in range(len(st)-1, -1, -1):
        d[ord(st[i])-65] = d[ord(st[i])-65] + pow(10, len(st)-i-1)


for i in range(len(d)):
    if d[i] == 0:
        continue
    array.append([d[i], chr(i+65)])

array.sort(reverse=True)

dic = dict()
value = 9
for a in array:
    dic[a[1]] = value
    value = value -1

result = 0
for string in strings:
    tmp = ""
    for s in string:
        tmp = tmp + str(dic[s])
    
    result = result + int(tmp)
    
print(result)