[Problem Solving] 백준 1339번 단어 수학 문제 풀이

백준 1339번 단어 수학 문제풀이에 대해서 알아보겠습니다. 문제 해설은 다음의 링크를 확인하여 주시기 바랍니다.

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

1339번: 단어 수학

 

해당 문제는 그리디 유형의 문제로 최적의 해결 방법에 대해서 고민해야 합니다. 처음 생각한 방법은 높은 자릿수 (백의 자릿수가 십의 자릿수보다 크다는 말)에 위치한 알파벳들에게 높은 숫자를 부여하는 것을 생각했습니다.

 

하지만 이 경우에 n = 10, data=[ABB, BB, BB, BB, BB, BB, BB, BB, BB, BB]이라는 반례가 존재합니다. 기존에 생각한 방법에 따르면 A=9, B=8이 되어 결괏값이 1780이 됩니다. 하지만 A=8, B=9로 결과를 계산하면 결괏값은 1790이 됩니다.

 

따라서 후자의 방법은 각 알파벳에 대해서 가중치를 부여하는 것으로 해결할 수 있습니다. 자릿수에 따라 가중치를 부여하면 A=100, B=110이 되므로 B가 더 큰 숫자를 부여받아야합니다. 따라서 해결방법은 다음과 같습니다. 이때 data_dict은 가중치를 저장하는 딕셔너리, answer_dict은 가중치의 크기에 따라 9부터 숫자들을 저장해주는 딕셔너리입니다.

 

1. 알파벳의 자릿수에 따른 가중치를 data_dict에 저장한다.
2. data_dict를 가중치에 key값으로 내림차순 정렬한다.
3. answer_dict에 가중치가 큰 알파벳에 따라 숫자를 부여한다.
4. answer_dict에 저장된 값을 이용하여 알파벳을 숫자로 바꿔준다.
5. 숫자로 바꾼 알파벳을 모두 더해준다.

위의 과정을 코드로 구현하면 다음과 같습니다.

 

# baekjoon No.1339 word math
n = int(input())

data = []
answer, count = 0, 9
data_dict, answer_dict = {}, {}

for i in range(n):
  data.append(list(map(str, input())))
  data[i].reverse()

for item in data:
  for i in range(len(item)):
    if data_dict.get(item[i]) is None:
      data_dict[item[i]] = 10 ** i;
    else:
      temp = data_dict.get(item[i])
      data_dict[item[i]] = temp + 10 ** i;
      
data_dict = sorted(data_dict.items(), key=lambda x: x[-1], reverse=True)

for item in data_dict:
  if answer_dict.get(item[0]) is None:
    answer_dict[item[0]] = count;
    count -= 1;

for item in data:
  temp_str = ''
  item.reverse()
  for i in range(len(item)):
    temp_str += str(answer_dict.get(item[i]))
  answer += int(temp_str)

print(answer)