[백준] 1339번 - 단어 수학

1차

아이디어

1) 주어진 단어 길이순으로 내림차순 정렬
2) 제일 긴 단어의 큰 자릿수부터 0~9중 max값을 알파벳마다 지정해준다.
알파벳과 숫자의 매칭은 dict를 사용하면 될 것 같다.

코드

N = int(input())
num = list(range(10))
alpha = []
tmp = {}

for _ in range(N):
    alpha.append(input())

alpha.sort(key = lambda x : len(x), reverse=True)

for i in range(N):
    for j in range(len(alpha[i])):
        val = alpha[i][j]
        if len(tmp) == 0:
            tmp[val] = str(max(num))
            num.remove(max(num))
        else:
            if val in tmp:
                continue
            else:
                tmp[val] = str(max(num))
                num.remove(max(num))
result = 0
for i in range(N):
    tmpresult = ""
    for j in range(len(alpha[i])):
        tmpresult += tmp[alpha[i][j]]
    result += int(tmpresult)
print(tmp)
print(result)

2차

아이디어

1차 아이디어에서 살짝 변형하여 (알파벳,자릿수)로 묶어 정렬한다.

코드

N = int(input())
num = list(range(10))
words = []
alpha = []
tmp = {}

for i in range(N):
    word = input()
    words.append(word)
    for j in range(len(word)):
        alpha.append((len(word)-j,word[j]))

alpha.sort(key=lambda x : x[0],reverse=True)

for a in alpha:
    if a[1] in tmp: # 알파벳과 0~9 매칭
        continue
    else:
        tmp[a[1]] = str(max(num))
        num.remove(max(num))

result = 0
for i in range(N):
    tmpresult = ""
    for j in range(len(words[i])):
        tmpresult += tmp[words[i][j]]
    result += int(tmpresult)

print(result)

반례
2
AB
BB
정답 = 188
출력결과 = 186

최종

아이디어

자릿값에 해당하는 값을 아예 계산해주는 건 어떨까? 라는 생각이 들었다. 위에 언급한 반례를 예시로 들자면 A = 10 B = 12이므로 B가 더 큰 값을 배정 받아야 하는 것이다. 그렇게 된다면 반례의 경우도 해결해줄 수 있겠다는 생각이 들었다.
1) 단어를 입력받는다.
2) 자릿값을 계산하여 해당 알파벳에 값을 배정해준다.
3) 이를 내림차순 정렬한다.
4) 값이 큰 알파벳부터 0-9중 남은 값들 중 큰 값부터 배정해준다.
5) 단어를 숫자로 치환해준다.

코드

N = int(input())
num = list(range(10))
words = []
tmp = {}
new = {}

for _ in range(N):
    words.append(input())

for word in words:
    for i in range(len(word)):
        if word[i] in tmp:
            tmp[word[i]] += (10**(len(word)-i-1))
        else:
            tmp[word[i]] = (10**(len(word)-i-1))

tmp = sorted(tmp.items(), key = lambda x : x[1], reverse= True)

num = 9
for i in range(len(tmp)):
    new[tmp[i][0]] = num
    num -= 1

result = 0
for word in words:
    tmpresult = ""
    for w in word:
        tmpresult += str(new[w])
    result += int(tmpresult)
print(result)