[백준 1339 골드4] 단어 수학

www.acmicpc.net/problem/1339

1339번: 단어 수학

해결방안

• 그리디(Greedy)를 이용한 방식 사용

알고리즘

1. 들어오는 단어들을 숫자로 나눔

   • abc => 100a + 10b + c
2. 각 문자들을 10의 배수에 대한 딕셔너리로 처리해서 넣어줌
   
   • abc라면, a에는 100, b에는 10, c에는 1
3. 딕셔너리 아이템의 value들을 가지고 내림차순으로 정렬 시킨 리스트 생성
4. 리스트를 돌면서 9부터 줄여가며 곱해줌
   • 9부터 줄여가는 이유는 최대값이 9이기 때문

핵심 팁

• Greedy 문제
  • 유사한 문제 
    • 거스름돈
• 각 경우의 최적의 해를 찾는 것이 중요
• 어떤 알파벳이 가장 큰 값이 들어가는지 굳이 고려할 필요 없음
  • 어차피 순서에 상관없이 값이 가장 큰 곳에 넣을 수 있는 가장 큰 값을 넣으면 되기 때문

 

n = int(input())
data = list()
for _ in range(n):
    e = input()
    data.append(e)
total = dict()
for ele in data:
    for i in range(len(ele)):
        dec = 10 ** (len(ele) - i - 1)
        if ele[i] in total:
            total[ele[i]] += dec
        else:
            total[ele[i]] = dec
num_list = sorted(total.items(), key=lambda x: x[1], reverse=True)
init_count = 9
sum = 0
for i in num_list:
    sum += i[1] * init_count
    init_count -= 1
print(sum)

 

 

*퍼가신다면 출처와 댓글 부탁드립니다.

*더 많은 자료는 아래 github에 있습니다

https://github.com/griffinGC/Algoritm_PS

https://github.com/griffinGC/TIL_Public