[백준]1339번 단어 수학 - 그리디

 

n = int(input())

word = []
for i in range(n):
    word.append(input())

digit = {}

for each_list in word:
    cnt = 0
    for i in each_list:
        if i not in digit:
            digit[i] = 10 ** (len(each_list) - cnt - 1) # 10의 거듭제곱 형태로 자릿수 설정
        else:
            digit[i] += 10 ** (len(each_list) - cnt - 1) # 자릿수 * 등장 횟수 누적
        cnt += 1

digit = sorted(list(digit.values()), reverse=True) # 내림차순으로 정렬

sum = 0
for i in range(len(digit)):
    sum += digit[i] * (10 - i -1) # 누적 자릿수 * 숫자 할당
print(sum)

 

코드 설명

word 리스트에 알파벳들을 전부 입력 받는다. 그 후 자리수를 위한 digit 딕셔너리를 선언한다.

예를 들어 ABC 인 경우 A는 100, B는 10, C는 1의 자릿수를 갖는다. 만약 ABC ABC 와 같이 2번 등장한다면 누적 값을 판별해야 하므로

A는 200, B는 20, C는 2의 digit 값을 가지게 된다. 그 후에 내림 차순으로 정렬하고 9, 8, 7 순서대로 값을 할당하며 더해준다.

 

 

Point : 각 알파벳에 맞는 자릿수를 설정하는 방식이 필요하다. 숫자의 길이에 따라 알맞은 자리 수를 설정하여 준다. 

주의할점은 누적으로 자릿수를 설정해주어야 낮은 자릿수의 등장 횟수가 큰 자릿수를 이기는 경우를 해결할 수 있다.

또한 마지막에 9 8 7 6 이런식으로 자릿수가 큰 알파벳에 가장 큰 숫자를 할당하여야 한다.