백준 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이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.
출력
첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.
어떻게 접근해야 할까?
백준 문제들을 보면 항상 느끼는 것..!
머리로는 모두 이해했지만 코드를 쓰려고 하면 막막하다는 것이다
사실 탐욕법 문제는 주어진 상황에서의 최적의 해를 구하는 알고리즘이기 때문에
다른 알고리즘에 비해서 문제가 단순하다고 한다 ( 물론 그래도 난 잘 못한다 )
✏️ 첫 접근...!
처음에는 더 자릿수가 큰 수의 알파벳에 큰 수를 부여하는 방법을 생각하였다.
하지만 얼마 지나지 않아 아래 같은 문제점을 발견할 수 있었다.
문제점
ABC 1개와 BB 9개를 입력받은 경우를 생각해보자!
A = 9, B = 8, C = 7 이라면 987 + 88 * 9 = 1,779
A = 8, B = 9, C = 7 이라면 897 + 99 * 9 = 1,788
더 긴 단어의 앞 자리 알파벳이 큰 경우가
반드시 최댓값을 도출하지는 않는다는 것을 알 수 있다!
그렇기 때문에 더 긴 단어의 앞 자리 알파벳에 초점을 맞춘다기 보다
우리가 구해야하는 결과값에 초점을 다시 맞춰 보았다.
✏️ 두 번째 접근...!
ABC와 EF가 주어졌다고 가정해보자
ABC + EF 를 수식으로 표현하면 다음과 같다
(결과값) = 100 A + 10 (B+C) + 1 (C+F)
한 가지 경우만 더 표현해보자
ABB + AB 의 경우는 아래와 같다
(결과값) = 100 A + 10 (B+A) + 1 (2B)
이 결과값을 A, B 따로 묶게 되면 다음과 같다.
(결과값) = 110 A + 12 B
이로부터 착안한 아이디어는
A라는 Key를 만들어 110이라는 value를
B라는 Key를 만들어 12이라는 value를 할당한 뒤
value 값을 내림차순하여 순서대로
9.. 8.. 7.. 6.. . . . 과 같이 큰 수를 부여하는 것이다!
완성된 코드
n = int(input())
answer = 0
saving = {}
values = []
num = 9
for _ in range(n):
word = input()
for s in range(len(word)):
if word[s] in saving:
saving[word[s]] += 10 ** (len(word) - 1 - s)
else:
saving[word[s]] = 10 ** (len(word) - 1 - s)
# print(saving)
for i in saving.values():
values.append(i)
values.sort(reverse = True)
#print(values)
for j in values:
answer += num * j
num -= 1
print(answer)answer는 구하는 최종 답안
saving은 A : 111, B : 12 처럼 각 알파벳의 가중치를 저장한 딕셔너리
values는 saving에서의 value 값들을 관리할 빈 리스트이다 !
for _ in range(n):
word = input()
for s in range(len(word)):
if word[s] in saving:
saving[word[s]] += 10 ** (len(word) - 1 - s)
else:
saving[word[s]] = 10 ** (len(word) - 1 - s)
위 코드를 통해 알파벳이 처음 들어가는 경우에는
딕셔너리에 Key와 value를 해당 값으로 초기화해주며
알파벳이 딕셔너리에 존재하는 경우, 주어진 값에 더하도록 코드를 작성했다.
for i in saving.values():
values.append(i)
values.sort(reverse = True)
saving의 저장된 value 값들을 빈 리스트 values에 저장한 뒤
.sort(reverse = True) 를 통해 내림차순으로 정렬해준다.
for j in values:
answer += num * j
num -= 1
values 에는 가중치가 가장 큰 순서부터 내림차순으로 정렬되어 있을테니
9부터 시작하여 차례대로 1씩 감소시켜 곱한 값을 answer에 더해준다.
