BOJ 1339 : 단어 수학 (Python)

문제

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

1339번: 단어 수학

 

 

코드

import sys

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

alpha = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
num = [0]*26 #알파벳에 숫자를 할당했는지 여부
check = [0]*10 #숫자를 사용했는지 여부

array = [] #알파벳 문자열을 담음
for i in range(n):
    array.append(list(sys.stdin.readline().strip('\n')))
    array[i].reverse()

array.sort(key=len,reverse = True)


for i in range(len(array[0])-1,-1,-1): #가장 긴 문자열의 길이-1 부터 시작해서 0이 될 때까지 for문
    for j in range(n):
        if len(array[j]) > i: #문자열의 길이가 현재 i 보다 길다면
            if num[alpha.index(array[j][i])] == 0: #알파벳에 아직 숫자를 할당하지 않았다면
                for q in range(9,-1,-1): #숫자 사용 여부 확인 (큰 숫자부터 작은 숫자로)
                    if check[q] == 0: #해당 숫자를 아직 사용하지 않았다면
                        check[q] = 1 #사용했다고 1로 표시 후
                        num[alpha.index(array[j][i])] = q #알파벳에 해당 숫자를 할당
                        break
total = 0 

for i in range(n):
    array[i].reverse()
    temp = ""
    for j in range(len(array[i])):
        temp += str(num[alpha.index(array[i][j])]) #알파벳을 그에 해당하는 숫자로 변환 후에 temp에 넣음
    total += int(temp(
print(total)

 

 

풀이

자릿수가 큰 알파벳에 우선적으로 사용하지 않은 가장 큰 숫자를 부여한다.

 

ex)

아래와 같이 두개의 문자열이 있다고 가정한다. ( 두 문자열 모두 reverse가 된 상태라고 가정한다.)

str1 = A B C D

str2 = B F G

가장 긴 문자열의 길이는 len(str1) = 4 이므로 인덱스 3 (len(str1)-1)에서부터 0으로 순차적으로 접근한다.

 

1.

str1[3] = D 에 사용하지 않은 가장 큰 숫자인 9를 할당한다.

str2[3] 는 존재하지 않으므로 다음 인덱스로 넘어간다.

check = [0, 0, 0, 0, 0, 0, 0, 0, 0,1]

2.

str1[2] = C 에 사용하지 않은 가장 큰 숫자인 8을 할당한다.

str2[2] = G 에 사용하지 않은 가장 큰 숫자인 7을 할당한다.

check = [0, 0, 0, 0, 0, 0, 0, 1, 1, 1]

3.

str1[1] = B에 사용하지 않은 가장 큰 숫자인 6을 할당한다.

str2[1] = F에 사용하지 않은 가장 큰 숫자인 5를 할당한다.

check = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

4.

str1[0] = A에 사용하지 않은 가장 큰 숫자인 4를 할당한다.

str2[0] = B에는 이미 6이 할당돼 있으므로 끝낸다. (3번에서 진행)

check = [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]

 

정리하면

D = 9, C = 8, G = 7, B = 6, F = 5, A = 4 이 된다. 이 숫자들을 알파벳에 넣어서 정수로 변환해준다.

→ 문자열이 reverse 된 상태였으므로 다시 원본으로 돌려서 진행해야한다.

 

str1 = DCBA = 9864

str2 = GFB = 756

 

이므로 더하면 답은 9864 + 756 = 10620 이다. 

 

 

오류.. 반례....

10
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB

위와 같이 주어졌을 때 B = 9 , A = 8 이 되어야 정상인데 A가 자릿수가 가장 크다보니 A에 9가 우선적으로 들어가서 오답이 나온다.

10의 자리에 위치한 B가 10개 이상이면 더했을 때 B는 100의 자릿수가 되기 때문에 이를 고려해야할 필요가 있는데 도통 어떻게 구현해야할 지 감이 안온다. 

 

 

추가)

알파벳 하나 하나씩 문자열에서 위치하는 자릿수에 1을 더하는 식으로 숫자로 변환을 하고 나중에 큰 숫자부터 차례대로 부여하는 방식을 사용하면 된다.

예를 들어 A 가 만의 자리와 십의 자리에 위치한다고 가정하면 수로 변환하면 10010 가 된다. 위치하는 해당하는 자릿수에 1씩 더해주는 것이다.

이렇게 하면 알파벳이 여러 개인 경우에도 기여하는 정도가 어느 정도인지 판단할 수 있고 이 기여도에 따라서 큰 숫자를 부여하면 되는 것이다.