(파이썬)백준 1339번 : 단어수학

백준 1339번 : 단어수학
일단 문제에 문자들이 등장하면 살짝 쫄게되는 면이 있다. (나만그런가?)
하지만 별로 어렵지 않다는 것을 금방 알아챌 수 있다.

1. 일정 개수의 영단어를 입력받는다.
2. 각 알파벳에 가중치를 9부터 0까지 부여할 수 있다.
   예를 들어, A = 1, B = 2, C = 3이라면,
   ABC = 123, CCA = 331 로 계산된다.
3. 입력받은 단어들의 합의 최댓값을 구하라.

설계

일단 보자마자 든 생각은 '사용된 알파벳이 각각 몇개인지 모두 구해야겠다' 였다.
예를 들어,
ABC 에서는 A가 100번, B가 10번, C가 1번 사용된 것을 기록하고
CCA 에서는 C가 100번 + 10번, A가 1번 사용된 것을 기록한다.

이런식으로 모든 단어들에 대해 검사를 진행하고 많이 사용된 알파벳부터
높은 가중치를 부여해서 (사용횟수 X 가중치) 를 모두 구하면 될 것 같다.
이렇게 쓰고나니 그리디 문제라는 것이 보이기 시작한다.

가중치가 9부터 0이고 알파벳은 최대 10개 등장하니 간단히 해결할 수 있어 보인다.

구현

일단 단어들은 리스트에 입력받으면 될 것 같고,
알파벳은 사용횟수와 함께 저장해야 하니 ( key : value ) 형태의 딕셔너리 자료형을 사용하자.

Words = [] #단어들을 저장할 리스트
DICT = {} #알파벳은 dictionary 자료형 사용

#입력
for _ in range(int(input())):
    Words.append(list(input().strip()))

입력받은 단어들에 대해서 다음의 과정을 거쳐야 한다.

1. 단어에 속해있는 문자 ch의 자릿수(10,100,1000,...)를 구한다.
2. ch가 딕셔너리 key 중에 있으면, value를 자릿수 만큼 증가시킨다.
3. 아직 딕셔너리에 없으면, 딕셔너리에 자릿수와 함께 추가한다.

말로 설명하려니 더 어려워보인다. 코드를 보자.

#입력받은 단어들에 대해
for wd in Words :
    #단어의 각 자리에 대해
    for i in range(len(wd)):
        # ex) ABCD에서 A의 tmp_value = 1000
        tmp_val = 10 ** (len(wd) - 1 - i)
        #해당 알파벳이 딕셔너리에 이미 들어있는지 확인
        if wd[i] in DICT:
            DICT[wd[i]] += tmp_val #이미 있으면 value 증가
        else :
            DICT[wd[i]] = tmp_val #아직 없으면 key:value 추가

여기까지 거치고 나면,
딕셔너리에 알파벳들과 각각의 사용횟수가
key : value 형태로 저장되어있다.

이제 사용횟수가 큰 순서대로 꺼낼 수 있게 만들어야 한다.

최댓값만 출력하면 되는 문제이니
사용횟수가 가장 큰 알파벳이 A인지 Z인지는 중요하지 않다.

그래서, 딕셔너리의 (1) value값들만 뽑아서 리스트로 만들고
(2) 내림차순 정렬을 해주면 될 것 같다.
문법을 잘 모른다면 이참에 알아두면 좋을 것 같다.

#(1) 키값들을 리스트로 변환
Values = list(DICT.values())
#(2) 내림차순 정렬
Values.sort(reverse=True)

이제부턴 해설이 딱히 필요없을 것 같다.
Values의 각 요소에 가중치를 9부터 1씩 감소시키면서 곱해주고, 총합을 구하면 된다.

#가중치 mul, 9부터 0까지 1씩 감소
mul = 9
#총합이 결과
SUM = 0
for el in Values:
    SUM += el * mul
    mul -= 1
#결과출력
print(SUM)

전체코드

import sys
input = sys.stdin.readline

Words = [] #단어들을 저장할 리스트
DICT = {} #알파벳은 dictionary 자료형 사용

#입력
for _ in range(int(input())):
    Words.append(list(input().strip()))

#입력받은 단어들에 대해
for wd in Words :
    #단어의 문자들에 대해
    for i in range(len(wd)):
        #가중치 ex) ABCD에서 A는 1000의 가중치를 가짐
        tmp_val = 10 ** (len(wd) - 1 - i)
        #해당 알파벳이 딕셔너리에 들어있는지 확인
        if wd[i] in DICT:
            DICT[wd[i]] += tmp_val #이미 있으면 value 수정
        else :
            DICT[wd[i]] = tmp_val #아직 없으면 key:value 추가
#(1) 키값들을 리스트로 변환
Values = list(DICT.values())
#(2) 내림차순 정렬
Values.sort(reverse=True)

#가중치 mul, 9부터 0까지 1씩 감소
mul = 9
#총합이 결과
SUM = 0
for el in Values:
    SUM += el * mul
    mul -= 1
#결과출력
print(SUM)

끝으로

난이도 上 문제로 선정하기엔 조금 쉽지 않나 싶긴하다. 실제로 정답률도 꽤 높은 편이다.
1700번 문제가 다소 까다롭기 때문에 이 문제는 다소 가벼운 마음으로 고르긴 했다.
누구나 문법에만 익숙하다면 충분히 해결할 수 있는 문제니 다들 시도해봤으면 좋겠다.

질문과 피드백은 언제나 환영합니다.