[python] 백준 1339 단어수학

*포스팅 스타일 변경

친구 : 문제 푼 사람들 다들 천재인가봐 어떻게 저런 접근법을 바로 생각하지?? 난 못하겠던데.. 너무 어려워ㅠㅠ

음.. 친구에게 도움이 될지는 모르겠지만 한 문제를 풀때도 여러 시행착오를 겪은 뒤에 푸는 사람이 있다는 것을 알려주고 싶었습니다.

따라서 문제를 풀때 했던 생각들을 모조리 적어볼까 합니다. 

의식의 흐름을 적는거니까 난잡해질 가능성이 있습니다. 

 

문제 링크

www.acmicpc.net/problem/1339

1339번: 단어 수학

문제 설명

'N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.'

알파벳이랑 0~9까지의 수를 매칭하여 푸는 문제입니다. 

접근 방법

1. 특정 알파벳이 여러 번 등장한다면 그 우선순위를 적용하고 싶습니다.

   1. 그러나 1의 자리에서 5번 등장한 알파벳보다 10의 자리에서 1번 등장한 알파벳의 가중치가 높아야합니다.

   2. 이를 해결할 방법이 떠오르지 않아서 보류했습니다.

2. 1-1를 보면 최대한 큰 자리에 위치한 알파벳에게 가중치를 높게 부여해야함을 알 수 있습니다.

   1. 각 알파벳마다 가중치 부여 -> dictionary를 떠올렸습니다.

   2. ABCD가 있다면 A : 4,B : 3,...을 부여했습니다. 숫자가 클 수록 후에 높은 값을 할당받습니다.

      1. ABCD + CFG라고 하면 후자의 C에 의해 더 큰 값으로 갱신합니다.

   3. 내림차순으로 정렬을 하고 (그러면 높은 값이 먼저 위치) 9부터 각 알파벳에 숫자를 차례대로 할당해줍니다.

   4. 다음에는 할당한 숫자와 함께 수식 계산을 해주면 됩니다. 

작성한 소스코드는 이러합니다.

import sys
input = sys.stdin.readline

n = int(input())
a = [input().rstrip() for i in range(n)]
dic = {}
for i in range(n):
    for j in range(len(a[i])):
        if a[i][j] in dic:
            if dic[a[i][j]] < len(a[i]) - j:
                dic[a[i][j]] = len(a[i]) - j
        else:
            dic[a[i][j]] = len(a[i]) - j

dic = sorted(dic.items(),key = lambda x:x[1],reverse=True)
pri = 9
tmp = {}
for i in range(len(dic)):
    temp = list(dic[i])
    temp[1] = pri-i
    tmp[temp[0]] = temp[1]

sum = 0
for i in range(n):
    for j in range(len(a[i])):
        sum += tmp[a[i][j]]*(10**(len(a[i])-j-1))

print(sum)

 

사실 이렇게 풀면 틀렸습니다가 나옵니다.

1의 조건을 제대로 만족하지 못했기 때문입니다.

코드를 보면 아시겠지만 2-4를 표현하면서 1번 조건을 해결할 방법을 사용했습니다.

처음 방법 떠올릴때는 분명 몰랐는데 어찌된 영문인지 모르겠습니다.

 

소스 코드

import sys
input = sys.stdin.readline

n = int(input())
a = [input().rstrip() for i in range(n)]
dic = {}

for i in range(n):
    for j in range(len(a[i])):
        if a[i][j] in dic:
            dic[a[i][j]] += (10**(len(a[i])-j-1))
        else:
            dic[a[i][j]] = (10**(len(a[i])-j-1))

dic = sorted(dic.items(),key = lambda x:x[1],reverse=True)
priority = 9
sum = 0
index = 0
for key,value in dic:
    sum += (priority-index)*value
    index+=1

print(sum)

 

이쪽이 정답인 소스입니다.

이 경우에는 ABCD면 A:1000 B:100,....으로 할당이 됩니다.

예시를 하나 추가하여 ABAC는 A:1010 B:100,...이 됩니다.

여기도 가중치가 큰 값에 높은 숫자(9)를 주기 위해서 내림차순 정렬을 해줍니다.

sum 계산할때는 그저 1010*9를 해주면 되겠죠!!

 

저는 처음에 딕셔너리를 떠올렸기에 그를 이용했습니다만

다른 알파벳 다루는 문제들처럼 int alpha[26] = [0]*26을 이용해서 접근하셔도 됩니다!!