[Python] 1339번 : 단어 수학

 

문제 3줄 요약

1. 알파벳 대문자로 이루어진 문자열들을 더한다.

2. 각 알파벳은 0부터 9 사이의 숫자 중 하나로 대체한다.

3. 문자열 합의 최댓값은?

 

 

 

처음엔 떠오른 방법은

1. 수의 단위가 높은 곳에 있는 알파벳

2. 수의 단위가 같고 빈도수도 같다면, 그 다음으로 높은 단위에 있는 알파벳

 

이 두 가지 규칙을 적용하여 코드를 작성하고 제출하였다.

Ex) GCF + ACDEB = 만의 자리(A : 1), 천의 자리(C:1), 백의 자리(G:1, D:1), 십의 자리(C:1, E:1), 일의 자리(F:1, B:1)

→ 방향 순으로 9부터 차례대로 부여

 

제출하니..

런타임 에러는

-1까지 값이 내려가서 생긴 오류이고,

위의 규칙을 적용한 코드는 틀렸다고 나온다..

 

반례를 찾다보니,

10, ABB, BB, BB, BB, BB, BB, BB, BB, BB, BB

를 보고 아차 싶었다.

 

무조건 자리 수가 높다고 큰 값을 부여한다면,

남은 자리의 합이 더 높은 경우를 놓치는 것이었다.

 

따라서

수의 크기별로 카운트 해준 값을

연산해서 비교해주기로 하였다.

 

Ex) GCF + ACDEB = 만의 자리(A : 1), 천의 자리(C:1), 백의 자리(G:1, D:1), 십의 자리(C:1, E:1), 일의 자리(F:1, B:1)

A = 10000, C = 1000, G = 100, D = 100, C = 10, E = 10, F = 1, B = 1

→ 방향 순으로 9부터 차례대로 부여

 

이런 방식이라면,

위와 같은 반례를 통과하고 코드 또한 간단해져 속도가 매우 빠르게 통과한다!

 

 

from sys import stdin
from collections import defaultdict

if __name__ == "__main__":
    N = int(stdin.readline())
    alphabet_dict = defaultdict(int)
    result_dict = defaultdict(int)

	# 수의 자리에 따른 알파벳 카운트
    str_list = []
    for _ in range(N):
        str_list.append(str(stdin.readline().strip())[::-1])

    count_list = []
    for idx in range(8):
        count_list.append(defaultdict(int))

        for s in str_list:
            if len(s) > idx:
                count_list[idx][s[idx]] += 1

	# 각 알파벳이 가지고 있는 숫자의 합
    for idx in range(7,-1,-1):
        if len(count_list[idx]):
            for key in count_list[idx].keys():
                alphabet_dict[key] += count_list[idx][key]*(10**idx if idx!= 0 else 1)


	# 내림차순으로 정렬하고 문자열에 대체
    number = 9
    for key in dict(sorted(alphabet_dict.items(), key=lambda item:item[1], reverse=True)).keys():
        result_dict[key] = number
        number -= 1

    for i, string in enumerate(str_list):
        string = list(string)
        for idx,s in enumerate(string[::-1]):
            string[idx] = str(result_dict[s])
        str_list[i] = int(''.join(string))
        
        
    print(sum(str_list))

 

끝