[모각코] 210814 Today I Learned

1339번: 단어 수학 (acmicpc.net)

1339번: 단어 수학

 

** 틀린 알고리즘

N = int(input())    # 단어 개수
word = []   # 단어
for _ in range(N):
    word.append(input())

num = 9
dic = {}
word_num = [ str(0) for i in range(N)]    # 숫자로 바꾼 단어

while(True):
    max_len_word = 0
    for i in range(len(word)):
        if max_len_word < len(word[i]):    # 자릿수 큰 거 찾기
            max_len_word = len(word[i])
            index = i
    if max_len_word == 0:
        break
    w = word[index][0]
    word[index] = word[index][1:]   # 첫 번째 문자 삭제
    if w in dic:
        x = dic[w]
    else:
        dic[w] = str(num)
        x = str(num)
        num -= 1
    word_num[index] = word_num[index] + x
    
for i in range(len(word_num)):	# 숫자형으로 형변환
    word_num[i] = int(word_num[i])

print(sum(word_num))

 

처음 접근한 방법은 자릿수가 큰 단어의 알파벳부터 큰 수를 부여하는 알고리즘이다. 자릿수가 더 큰 단어를 가져와서 맨왼쪽 알파벳에 수를 부여하고 그 알파벳은 삭제하는 것이다. 테스트 케이스가 다 맞게 나와서 한 번에 맞은 줄 알고 기뻐했는데 제출하자마자 틀렸습니다가 나왔다. ㅎ 어디서 오류가 났나 천천히 생각해보니 내가 놓친 부분이 하나 있었다. 자릿수가 같을 경우 나는 먼저 저장한 단어에 수를 부여하게 되는데 그러면 최댓값이 나오지 않을 수 있다.

예를 들어,

2

ABC

BCD

input으로 이렇게 들어올 경우, 내 코드에서는 A=9, B=8, C=7, D=6 으로 수가 부여되어 최댓값으로 1863이 나오게 된다. 자릿수가 같은 경우로 먼저 저장된 A에 큰 수가 부여되었기 때문이다. 하지만 여기선 B에 9가 부여되어야 더 큰 값이 나올 수 있다. 수를 부여하려는 알파벳이 단어 안에 또 있을 경우도 생각해야 한다.

 

그래서 두 번째로 떠올린 방법은 각 단어에 자릿값을 부여하고 같은 알파벳끼리 값을 더해 최종적인 알파벳의 값을 구하여, 최종적으로 가장 큰 값을 가진 알파벳부터 차례대로 큰 수를 부여하는 것이다. 위 예시로 풀어보면 A=100, B=10, C=1 / B=100, C=10, D=1 이렇게 되어 최종 알파벳의 값은 A=100, B=110, C=11, D=1 이렇게 된다. 따라서, 가장 큰 값은 110으로 B에 9, A에 8, C에 7, D에 6을 부여하게 된다. 이렇게 했을 때 최댓값은 1873이 나오게 된다.

 

N = int(input())    # 단어 개수
word = []   # 단어
for _ in range(N):
    word.append(input())

dic = {}
for i in range(N):  # 자릿값 계산
    for j in range(len(word[i])):
        w = word[i][j]
        if w in dic:
            dic[w] = dic[w] + 1 * (10 ** (len(word[i]) - j-1))
        else:
            dic[w] = 1 * (10 ** (len(word[i]) - j-1))

dic = sorted(dic.items(), key=lambda x:x[1], reverse=True)  # value (자릿값) 기준으로 내림차순 정렬

num = 9
for i in range(len(dic)):   # 자릿값이 큰 알파벳부터 큰 수 부여
    for j in range(len(word)):
        word[j] = word[j].replace(dic[i][0], str(num))
    num -= 1

for i in range(len(word)):  # 문자열 정수형으로 형변환
    word[i] = int(word[i])

print(sum(word))