[백준][Python] 단어 수학

728x90

문제 요약

주어진 입력인 알파벳에 숫자를 대입하여 가장 큰 합을 찾아내는 것입니다.

분류는 브루트포스로 나와있지만 자릿수에 따라 바로바로 수를 대입한다고 생각하면 그리디 알고리즘이라 생각할 수 있습니다.

 

내가 문제 풀 때 생각했던 것

자릿수에 따른 숫자 대입이라 생각했습니다. 어짜피 6 + 7 이나 7 + 6 이나 같고 178 + 456 이나 158 + 476 이나 결과는 634로 같기 때문에 자릿수가 같을 때의 숫자는 상관 없다고 풀었습니다.

 

그래서 길이를 기준으로 정렬하고 길이가 가장 긴(= 자릿수가 가장 큰) 단어의 앞자리는 가장 큰 수인 9를 저장하고 앞자리만 없앴습니다. 그 다음으로 길이가 가장 긴 단어의 앞자리는 8을 저장하는 등 소거법으로 문제를 해결했습니다.

 

1차 풀이

from collections import defaultdict

N = int(input())
alphaList = [] # 주어진 단어 리스트
answer = [] # 정답
number = 9 # 넘버링
alpha = defaultdict(str) # 알파벳과 숫자를 연결시킬 딕셔너리
for i in range(10):
    alpha[str(9-i)] = '' # 딕셔너리 초기화
for i in range(N):
    put = input()
    alphaList.append(put)
    answer.append(list(put))
alphaList.sort(key=len, reverse=True) # 길이순으로 정렬
while(len(alphaList)!=0):
    if len(alphaList[0]) == 1: # 만약 단어가 1자리수라면
        if alphaList[0] in alpha.values() : # 만약 알파벳이 딕셔너리에 존재한다면
            alphaList.pop(0) # 앞자리 제거
            continue
        alpha[str(number)] = alphaList[0] # 알파벳을 숫자에 연결
        alphaList.pop(0)
        number -= 1
    else:
        if alphaList[0][0] in alpha.values() : # 만약 알파벳이 딕셔너리에 존재한다면
            alphaList[0] = alphaList[0][1:] # 앞자리 제거
            alphaList.sort(key=len, reverse=True)
            continue
        else: # 만약 알파벳이 딕셔너리에 존재하지 않는다면
            alpha[str(number)] = alphaList[0][0] # 앞자리 알파벳을 숫자에 연결
            alphaList[0] = alphaList[0][1:]
            number -= 1
        if alphaList[0] == '': # 앞자리를 제거하여 비었다면
            alphaList.pop(0) # 단어 제거
        alphaList.sort(key=len, reverse=True)

list_of_key = list(alpha.keys()) # 키 리스트
list_of_value = list(alpha.values()) # 값 리스트
SUM = 0
for i in answer:
    for j in range(len(i)):
        position = list_of_value.index(i[j]) # 값을 가지고 있는 키의 인덱스
        i[j] = str(list_of_key[position]) # 결국 숫자로 전환할 수 있다
    SUM += int((''.join(i))) # 수의 합
print(SUM)

 

 

틀림ㅋ

나와있는 예제를 모두 맞췄지만 반례에서 막혔습니다..

2시간을 봐도 모르길래 다른 사람의 풀이를 봤더니 제가 약간 다르게 풀었더군요..

저는 자릿수를 계산하긴 했지만 알파벳의 가중치를 생각해야하는 문제였습니다.

 

예를 들면

ABB + BB + BB + BB + BB에서 제 풀이대로라면 A = 9, B = 8이면 최댓값이지만 실제로는 A = 8, B = 9이면 최댓값이 나옵니다.

그 이유는 A * 100 보다 B * 11 * 5가 더 크기 때문입니다.

저는 이러한 가중치를 생각하지 못하고 자릿수만 생각하여 생긴 맹점으로 인해 틀리게 되었습니다.

 

2차 풀이

from collections import defaultdict

N = int(input())
alphaList = []
alpha = defaultdict(int)
for i in range(N):
    put = input()
    alphaList.append(put)
alphaList.sort(key=len, reverse=True)
while(len(alphaList)!=0):
    if len(alphaList[0]) == 1:
        if alphaList[0] in alpha.keys() :
            alpha[alphaList[0]] += 10 ** (len(alphaList[0])-1) # 해당 알파벳의 자릿수만큼 10의 제곱을 곱해줌
            alphaList.pop(0)
            continue
        alpha[alphaList[0]] += 10 ** (len(alphaList[0])-1)
        alphaList.pop(0)
    else:
        if alphaList[0][0] in alpha.keys() :
            alpha[alphaList[0][0]] += 10 ** (len(alphaList[0])-1)# 해당 알파벳의 자릿수만큼 10의 제곱을 곱해줌
            alphaList[0] = alphaList[0][1:]
            alphaList.sort(key=len, reverse=True)
            continue
        else:
            alpha[alphaList[0][0]] += 10 ** (len(alphaList[0])-1)# 해당 알파벳의 자릿수만큼 10의 제곱을 곱해줌
            alphaList[0] = alphaList[0][1:]
        if alphaList[0] == '':
            alphaList.pop(0)
        alphaList.sort(key=len, reverse=True)

alpha = sorted(alpha.values(),reverse=True)
SUM = 0
for i in range(len(alpha)):
    SUM += alpha[i] * (9-i)
print(SUM)

 

GCF + ACDEB

A 는 10000의 자리에서 1번 등장 = A * 10000

C는 1000의 자리에서 1번 + 10의 자리에서 1번 = C * 1010

G는 100의 자리에서 1번 등장 = D * 100 ...

 

이런식으로 해결하면 됩니다.