[BOJ] Q1339 단어 수학

[BOJ] Q1339 단어 수학

Question

Language: Python

Difficulty: Gold 4

주어진 문자열에 대해서, 문자열을 구성하는 알파벳을 숫자로 치환해서, 각각의 문자열들을 숫자로 변환 했을때, 숫자들이 가질 수 있는 최대값을 구하는 문제이다.

1. 처음에는 자리수만 높으면 된다고 생각했다. 그래서 아래와 같이 각 알파벳에 대해 최고 자리수만 저장하게 되었다.

conversion=defaultdict(int)
    
for string in strings:
    length=len(string)
    for i in range(length):
        conversion[string[i]]=max(conversion[string[i]],length-i)

temp_list=[(value,index) for index,value in conversion.items()]
temp_list.sort(key=lambda x: -x[0])

하지만 위와 같이 생각하게 되면 아래와 같은 반례가 존재가 발생한다.

3
BCA
ABC
ACB

정답: A=9,B=8,C=7 2844 오답: A=8,B=9,C=7 2754

1. 오 그러면, 최고 자리수 위치에 있는 알파벳의 갯수를 구하는 식으로 생각하였다.

conversion={alphabet : [0,1] for alphabet in set(alpha_sets)}
    
    for string in strings:
        length=len(string)
        for i in range(length):
            if length-i == conversion[string[i]][0]:
                conversion[string[i]][1]+=1
            conversion[string[i]][0]=max(conversion[string[i]][0],length-i)


    temp_list=[(value,index) for index,value in conversion.items()]
    temp_list.sort(key=lambda x: (-x[0][0],-x[0][1]))

하지만 위의 경우 또한 아래와 같은 반례가 존재한다.

10
ABB
BC
BC
BC
BC
BC
BC
BC
BC
BC

정답: A=8,B=9,C=7 1772 오답: A=9,B=8,C=7 1771

1. 곰곰히 생각해보면, 최고 자리수, 각각의 자리수에 해당하는 개수를 모두 고려했을 때 나오게 되는 것이 바로 해당 알파벳들의 위치값들을 모두 더해서 구성하는 방식이다.

즉, ABCDD와 같이 있을때, A=10000, B=1000,C=100,D=11로 만들게 되면, 정확한 비교가 가능해진다.

Solution

from collections import defaultdict
def solution():
    conversion=defaultdict(int)

    digits=[10**i for i in range(8)]
    
    for string in strings:
        length=len(string)
        for i in range(length):
            conversion[string[i]]+=digits[length-i-1]

    temp_list=[(value,index) for index,value in conversion.items()]
    temp_list.sort(key=lambda x: (-x[0]))

    num=9
    for value,index in temp_list:
        conversion[index]=num
        num-=1
    
    result=0
    
    for string in strings:
        length=len(string)
        for i in range(length):
            string[i]=str(conversion[string[i]])
        result+=int("".join(string))

    return result 

if __name__ == "__main__":
    N=int(input())
    alpha_sets=[]
    strings=[list(input().strip()) for _ in range(N)]
    
    print(solution())