[백준] 1339번: 단어 수학 - Python

링크: https://www.acmicpc.net/problem/1339

1339번: 단어 수학

처음 생각

• 길이를 기준으로 정렬
• for문을 돌며 이웃한 요소의 길이차를 비교
• 길이가 다르면 그 다른 길이만큼의 알파뱃에 큰수부터 부여
• 길이가 같다면 길이가 같은 문자열이 더 있는지 계속 확인
• 확인이 끝난 후 각 문자열의 맨 앞에있는 알파뱃을 가지고 누구의 알파뱃이 이웃한 요소에서 먼저 나오는지 확인.
• 먼저 나오는 알파뱃부터 큰 수 부여

이런 식으로 가장 큰수를 찾아보려 했다..

하지만 구현하는 중간 중간 처리해야 할 예외가 너무 많아 악의 구렁텅이에 빠지는 느낌이 들기 시작했다.

 

결국 서치하여 정답을 봤고 아래는 정답 코드이다.

 

코드(서치)

import sys

n = int(sys.stdin.readline())

alpha = [] # 단어를 저장할 리스트
alpha_dict = {} # 단어 내의 알파벳별로 수를 저장할 딕셔너리
numList = [] # 수를 저장할 리스트

for i in range(n): # 단어를 입력받음
    alpha.append(sys.stdin.readline().rstrip())

for i in range(n): # 모든 단어에 대해서
    for j in range(len(alpha[i])): # 단어의 길이만큼 실행
        if alpha[i][j] in alpha_dict: # 단어의 알파벳이 이미 dict에 있으면
            alpha_dict[alpha[i][j]] += 10 ** (len(alpha[i])-j-1) # 자리에 맞게 추가 ( 1의 자리면 1 )
        else:   # 자리에 없으면 새로 추가 ( 10의 자리면 10 )
            alpha_dict[alpha[i][j]] = 10 ** (len(alpha[i])-j-1)

for val in alpha_dict.values(): # dict에 저장된 수들을 모두 리스트에 추가
    numList.append(val)

numList.sort(reverse=True) # 수들을 내림차순 정렬

sum = 0
pows = 9
for i in numList: # 첫 번째 부터 가장 큰 부분을 차지하므로 9를 곱해준다
    sum += pows * i
    pows -= 1
# 내려갈수록 그 알파벳이 차지하는 비중이 적으므로 -1 
print(sum)

설명

그리디 알고리즘을 적용시킨 문제인데

각 단어에서의 자리에 대한 정보를 가진 수를 딕셔너리에 저장한다.

{ 'A' : 100, 'B' : 1010, 'C': 1 ... }

모든 단어를 위와같이 저장 후 딕셔너리의 value값을 가져와 내림차순 정렬을 하면 가장 큰 수? 큰 비율을 가진 것부터 정렬이 된다.

이 리스트의 첫 수부터 숫자를 곱해주면 가장 큰 경우가 나오게 된다.

 

마무리

• 지금 다시 읽어보니 확 이해가 된다.
• 그리디... 만만치 않은 유형이다.
• 그치만 확실히 정확한 풀이법을 인지하게 된다면 이보다 쉽고 빠른 유형이 없다..
• 박치기로 많이 푸는게 답인가보다...