[백준][그리디] 1339. 단어 수학

1339. 단어 수학

1339번: 단어 수학

 

• 내 풀이
  • 무조건 앞자리수에 큰값을 주면 된다고 생각함
  • -> 뒤의 어떤 문자가 전부 더해진 후가 앞자리 문자보다 커질 수 있는 문제 발생

from collections import defaultdict

n = int(input())
m = 0
all_lst = []
for _ in range(n):
    tmp = input()
    all_lst.append(tmp)
    m = max(m, len(tmp))

alpha = [[] for _ in range(m)]
cnt = defaultdict(list)
for lst in all_lst:
    for i, v in enumerate(reversed(lst)):
        alpha[i].append(v)
        if cnt[v]:
            cnt[v] += 1
        else:
            cnt[v] = 1

alpha.reverse()
num = 9
total = defaultdict(list)
result = []
for alst in alpha:
    tmp = []
    for a in alst:
        tmp.append((a, cnt[a]))
    tmp.sort(key=lambda x: x[1], reverse=True)
    result.append(tmp)

    for t in tmp:
        if total[t[0]]:
            continue
        total[t[0]] = num
        num -= 1

answer = 0
for i, tmp in enumerate(result):
    for t in tmp:
        answer += total[t[0]]*(10**(m-i-1))

print(answer)

#반례
10
ABB
BC
BC
BC
BC
BC
BC
BC
BC
BC

# 내코드 :1771
# 답: 1772
# A:8, B:9, C:7 이 되어야함

 

 

• 다른 사람 풀이
  • 📍처음 값을 입력받을때 자릿수마다 가중치값을 더해서 저장한 후 그걸로 더 큰값을 판단
  • -> 위 방법 참고하여 코드 수정

from collections import defaultdict

n = int(input())
m = 0
all_lst = []
alpha = defaultdict(int)
for _ in range(n):
    tmp = list(input().rstrip())
    all_lst.append(tmp)

    for i in range(len(tmp)-1, -1, -1):
        alpha[tmp[i]] += 10**(len(tmp)-i-1)
    m = max(m, len(tmp))

alpha_lst = sorted(alpha.items(), key=lambda x: x[1], reverse=True)
num = 9
answer = 0
for a in alpha_lst:
    answer += num*a[1]
    num -= 1

print(answer)