[백준] 1339번 단어수학 Python 파이썬 풀이

1339번: 단어 수학

---

[문제]

---

[코드]

import sys
input = sys.stdin.readline

reference = {}
N = int(input())
words = []
for _ in range(N):
    word = input().rstrip()
    words.append(word)
    for j in range(len(word)):
        if word[j] in reference:
            reference[word[j]] += 10 **(len(word)-j-1)
        else:
            reference[word[j]] = 10 **(len(word)-j-1)

total = list(reference.values())
total.sort(reverse=True)

max_n = 9
result = 0
for i in total:
    result += i * max_n
    max_n -= 1

print(result)

---

[코드]

오랜만에 찾아온 백준 알고리즘 문제 풀이...

문제 유형 : 그리디(Greedy) 알고리즘
백준 난이도 : 골드4
체감 난이도 : 실버 1 ~ 골드 5

 

오랜만에 문제를 풀어서 그런지 초반에 약간 실수를 했다.

그러나 간단하게 접근하니까 쉽게 풀리는 문제였다.

 

문제의 핵심 : 

 

우리가 얻고자 하는것은 알파벳들을 더해서 얻을 수 있는 최댓값을 만들어 줄수 있는

변환 숫자표를 만들어내는 것 이라고 오해할 수 있지만!! 

결국 얻고자 하는 것은 알파벳 합의 최댓값이다. 

따라서 각 알파벳이 무슨 숫자로 변환되는지를 저장하는 프로세스는 중요하지 않다

 

우리가 집중해야하는 것은 알파벳 각 자릿수 ex) 천의자리, 백의자리

즉, 자릿수가 큰 위치에 있는 알파벳일 수록 높은 숫자를 부여하면된다.

 

처음에는 이부분에서 약간막혔다

예를 들어  AAA, BBB, BBA 와 같이 단어가 주어지고 가장큰 100자리에는 A, B가 있는데

이들에게 무슨 수를 주는지 결정해야하는 기준이 각 자리에서 Count해서 가장 많은 알파벳에게 주는 것이라고

생각을 했는데 이러면 단어가 주어질때 마다 count를 해야해서 코드의 구상이 복잡해졌다.

 

그러나 

핵심은 합에 있었다.

즉,

AAA -> 100 + 10 + 1

BBB -> 100 + 10 + 1

BBA -> 100 + 10 + 1

A : (100 + 10 + 1 + 1) 

B : (100 + 10 + 1 + 100 + 10) 

 

따라서 A가 B보다 크기 때문에 (합의) B의 모든 합에 9를 곱하고 A의 모든 합에 8을 곱한다음

더해주면되는 간단한 로직이었다.

 

 

구현 :

import sys
input = sys.stdin.readline

reference = {}
N = int(input())
words = []

reference : 각 단어에서 알파벳 자릿수를 저장할 딕셔너리

N : 총 단어 갯수

words = 단어를 저장할 리스트 (생각해보면 사실 필요없음, 삭제해도 무방)

 

for _ in range(N):
    word = input().rstrip()
    words.append(word)
    for j in range(len(word)):
        if word[j] in reference:
            reference[word[j]] += 10 **(len(word)-j-1)
        else:
            reference[word[j]] = 10 **(len(word)-j-1)

각 단어의 수만큼 단어를 input으로 받는 for문을 생성

그리고 words.append(word)는 추후에 사용되지 않기 때문에 리뷰 하면서 생각했는데 삭제해도 무방

 

두번째 for문 : input으로 받은 단어의 길이 j만큼 반복

만약 input단어 word[j] 위치에 있는 알파벳이 처음 만들어 놓은 reference 딕셔너리에 있다면  자릿수 만큼 있던 숫자에 +

만약 input단어 word[j] 위치에 있는 알파벳이 처음 만들어 놓은 reference 딕셔너리에 없다면 알파벳과 그 자릿수 추가 

 

total = list(reference.values())
total.sort(reverse=True)

max_n = 9
result = 0
for i in total:
    result += i * max_n
    max_n -= 1

print(result)

이렇게 만들어지는 reference의 values를 리스트로 생성하고 오름차순으로 정렬

 

그리고 max_n : 9 -> 가장 높은 수 를 9로지정

우리의 결과값( 최댓값) : 0으로 지정

total (values가 오름차순으로 정렬된 리스트)를 for문으로 돌면서 

각 자리에 max_n을 곱해서 result에 저장 

그리고 한번돌때마다 max_n을 1씩 빼준다

ex) total = [ 10001, 1001, 111, 10, 1]
 i) 10001 * 9 = 90009, result = 90009
 ii) 1001 * 8 = 8008, result = 98017
 iii) 111 * 7 = 777, result = 98794
 ...... 진행