[백준] 1132번 합 ★

💡문제접근

• [[백준] 1339번 단어 수학] 문제와 유사한 형태의 그리디 알고리즘 문제다.
• 하지만 그 문제와 다른 점이 있다. 이 문제에서는 0으로 시작하는 숫자는 존재하지 않는다는 것이다.
• 맨 처음 알파벳에 대응하는 값이 0이 나오는지를 확인하기 위해서 first 배열을 만들어 맨 처음 알파벳을 배열에 넣는다. 사전에 들어가는 키의 값의 개수가 10개 미만이라면 1 ~ 9 사이의 값이 사전의 값에 들어가게 되고 이 때는 맨 앞 숫자의 값이 0이 나올 일이 없어 문제가 되지 않는다.
• 하지만 사전에 들어가는 키의 값의 개수가 10개라면 0 ~ 9 사이의 값이 사전의 값에 들어가게 되는데 이 때, 0이 맨 앞 숫자의 값으로 나올 수 있다. 이 부분을 해결하는데 많은 시간이 소요되었다.

💡코드(메모리 : 31388KB, 시간 : 40ms)

import sys
input = sys.stdin.readline

N = int(input())
answer = []
first = []
my_dict = {}
for _ in range(N):
    i = 1
    word = input().strip()
    answer.append(word)
    first.append(word[0])
    for t in range(len(word)):
        if word[t] not in my_dict:
            my_dict[word[t]] = 10 ** (len(word) - i)
        else:
            my_dict[word[t]] += 10 ** (len(word) - i)
        i += 1

if len(list(my_dict.keys())) < 10:
    result = 0
    val = 9
    values = sorted(my_dict.items(), key = lambda x : -x[1])
    for i in values:
        result += i[1] * val
        val -= 1
    print(result)
# 맨 앞자리에 0이 나올 수 있는 경우
else:
    result = 0
    m = 9
    values = sorted(my_dict.items(), key = lambda x : -x[1])
    for i in values:
    	# 값을 기준으로 내림차순 정렬한 상태에서 0이 나오는 문자와 그 전 문자의 값을 바꿔줘야하므로 0이 나오는 문자와 가장 가까운 문자를 tmp에 할당
        if i[0] not in first:
            # ABCDEFGHIJ → I
            tmp = i[0]

    for i in values:
        # 만약 tmp 즉, I가 나오면 계산하지않고 넘어간다.
        # 그게 아니라면 합을 계속 누적한다.
        if i[0] != tmp:
            result += i[1] * m
            m -= 1
        else:
            continue
    print(result)

💡소요시간 : 1h 51m