백준 1339번: 단어 수학

백준 1339번: 단어 수학

1339번: 단어 수학

 

백트래킹을 활용한 풀이도 있지만 그보다 덧셈식을 활용한 풀이가 더 좋다고 생각하여 덧셈식을 활용하여 풀었다

• N = 2, GCF + ACDEB 와 같은 입력이 주어진다고 가정하자
• 각 알파벳과 자릿수를 계산하면 ((G * 100) + (C * 10) + (F * 1)) + ((A * 10000) + (C * 1000) + (D * 100) + (E * 10) + (B * 1)) 와 같이 나타낼 수 있다
• 계수를 알파벳에 따른 내림차순으로 정리하면 (A * 10000) + (C * 1010) + (D * 100) + (G * 100) + (C * 10) + (E * 10) + (B * 1) + (F * 1) 와 같이 나타낼 수 있다
• 계수가 큰 알파벳부터 9부터 0까지 수를 부여하면 된다

아래는 파이썬 코드이다

 

	import operator
	n = int(input())
	a = {}
	for i in range(n):
	tmp = list(input())
	for j in range(len(tmp)):
	# 딕셔너리 a에 이미 알파벳이 있다면 기존 value에 더한다
	if tmp[j] in a.keys():
	a[tmp[j]] += 10 ** (len(tmp) - j - 1)
	# 딕셔너리 a에 알파벳이 없다면 새로 key를 추가하고 value에 더한다
	else:
	a[tmp[j]] = 10 ** (len(tmp) - j - 1) # 자릿수 계수는 len(tmp) - j - 1 이다
	rep = sorted(a.items(), key=operator.itemgetter(1)) # 자릿수 계수가 큰 알파벳 순으로 정렬한다
	ans = 0
	num = 9
	for i in range(len(rep) - 1, -1, -1):
	ans += num * rep[i][1] # 자릿수 계수를 곱
	num -= 1
	print(ans)

view raw BOJ_1339.py hosted with ❤ by GitHub