[백준] 1339. 단어수학

https://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이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

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

내 풀이

내 풀이는 매우 어렵기 그지 없는데, 코드와 함께 설명하겠다.

# 알파벳을 key로 놓고 value를 모두 0으로 초기화한다.
alpha = {'A': 0, 'B': 0, 'C': 0, 'D': 0, 'E': 0, 'F': 0, 'G': 0, 'H': 0, 'I': 0, 'J': 0, 'K': 0, 'L': 0, 'M': 0, 'N':0, 'O': 0, 'P': 0, 'Q':0, 'R':0, 'X':0, 'T':0, 'U':0, 'V':0, 'W':0, 'X':0, 'Y':0, 'Z':0}

# 입력, 단어의 개수
num = int(input())
# 입력, 단어
word_num = [input() for n in range(num)]

# 단어와 단어의 길이를 dictionary 형태로 저장하기 위한 변수
word_num_num = {}
# 모든 단어의 길이의 합
total_num = 0
for word in word_num:
    word_num_num[word] = len(word)
    total_num += len(word)

numbering = 9 
while True:

    # 길이에 따라 내림차순 정렬
    res = sorted(word_num_num.items(), key=(lambda x: x[1]), reverse=True)

    # res = [('ACDEB', 5), ('GCF', 3)]
    # res[0][0]: 정렬 결과의 맨 처음 값으로 가장 길이가 긴 값
    if res[0][0] == '':
        total_num = 0
    # 검사할 단어가 있는지 없는지를 판단
    if total_num == 0:
        break
    
    # [('ACDEB', 5), ('GCF', 3)]에서 'ACDEB'의 'A'에 대해 처음 검사를 진행

    # 이때 'A'가 이미 0이 아닌 다른 값을 가지고 있다면 'A'에 대해서는 검사하지 않음
    if  alpha[res[0][0][0]] == 0:
    	# alpha['A'] = numbering 이런 식으로 alpha 딕셔너리에 있는 알파벳의 값을 할당한다.
        alpha[res[0][0][0]] = numbering

 	# word_num_num에서 'ACDEB'를 지우고 'CDEB'를 append한다.
        word_num_num[res[0][0][1:]] = res[0][1] - 1
        del(word_num_num[res[0][0]])    
        # 'A'에 numbering값을 넣었으니 1 감소시킨다.
        numbering -= 1
        # 'ACDEB' 대신 'CDEB'가 들어갔으니 'A'에 대한 단어의 길이를 total_num에서 빼줘야한다.
        total_num -= 1
    else :
        # 이미 값이 할당된 알파벳을 처리하는 부분
        word_num_num[res[0][0][1:]] = res[0][1] - 1
        del(word_num_num[res[0][0]])

        total_num -= 1

# 할당된 알파벳으로 단어를 숫자로 바꾸는 부분
real_num = []
for word in word_num:
    real = ''
    for w in word:
        real += str(alpha[w])
    real_num.append(int(real))

print(sum(real_num))

정렬 -> 단어 하나 지우기 -> 정렬 -> 단어 하나 지우기 -> 정렬 -> 단어 하나 지우기 ....가 계속 반복되는 것인데, 이러면 답을 얻을 수는 있다. 근데 아마 틀렸을 거다..

물론 제출해서는 런타임에러를 먹었다.

공부

에러를 고치기 위해 다른 분들의 코드를 참고하고자 했는데, 이 분 코드를 보니 내가 얼마나 한심하게 짰나 하는 생각이 들어서 위의 코드를 고치기보다는 아래 코드를 공부하기로 했다.

# 입력, 단어의 개수
t = int(input())

ss = []

# 입력, 단어
for _ in range(t):
    ss.append(input())

# 26개의 알파벳을 무식하게 dictionary에 때려넣은 나와는 다르게 알파벳 순서로 하셨다.
# 예) A, B, C... -> 0번째, 1번째, 2번째
alphabet = [0 for i in range(26)]

for s in ss:
    i = 0
    while s:
    	# 가장 뒤부터 시작해서 1, 10, 100 .. 이렇게 더해가는 것.
        now = s[-1]
        alphabet[ord(now) - ord('A')] += pow(10, i)
        i += 1
        s = s[:-1]
# 위의 for문을 다 돌리고 alphabet을 출력해보면 다음과 같다.
# alphabet = [10000, 1, 1010, 100, 10, 1, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
alphabet.sort(reverse=True)
# 그리고 위의 alphabet을 정렬하고 출력하면 다음과 같다.
# alphabet = [10000, 1010, 100, 100, 10, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
print(alphabet)
ans = 0
for i in range(9, 0, -1):
    ans += i * alphabet[9-i]

print(ans)

위와 같이 풀 경우 다음과 같은 입력에도 문제없이 풀 수 있을 것이다.

3
GCF
ACDEB
B

내가 푼 코드로 위의 입력을 넣을 경우 B에 F보다 작은 값이 들어갈 경우 정답이 아니게 된다. 즉, 단어의 길이로만 판단하기 때문에 다른 알파벳들에 대한 숫자를 모두 할당한 후 'F', 'B', 'B'와 같은 상황이 연출되었을 경우 B가 더 많이 나왔으므로 B에 더 큰 값이 들어가야하지만, 그렇게 들어갈 지는 모른다. (다른 조건이 추가되어야 할 것이다.)

그런데 위와 같이 풀면 위와 같은 걱정은 할 필요도 없으니 좋은 코드같다.

그리디 문제가 심각해서 풀기 시작했는데, 진짜 심각한 것 같다.. 더 열심히 해야겠다..