greedy 알고리즘

문제출처 : https://www.acmicpc.net/problem/1339

틀렸던 풀이과정

1. 문자열을 하나씩 받으며 leng에는 해당 문자열의 자릿수를, cnt에는 갯수를 저장해주었다.

2. alpha라는 리스트를 정렬하는데 첫 번째 기준으로 leng의 값, 두 번째 기준으로는 cnt의 값으로 하였다.
   (이 곳이 틀린 포인트이다.)

3. 결과적으로
   10
   ABB
   BB
   BB
   BB
   BB
   BB
   BB
   BB
   BB
   BB
   의 테스트 케이스에서 내가 짯던 코드로는 1780의 값이(A : 9, B : 8) 나왔지만
   정답은 (A : 8, B : 9) 인 1790이 최대값이다.

틀린코드

n = int(input())
leng = {}
cnt={}
dic={}
alpha=[]
answer=[]
final_answer=[]
for i in range(n):
    num = input()
    answer.append(num)
    for j in range(len(num)):
        if num[j] not in leng:
            leng[num[j]]=1*len(num[j:])
        else:
            temp = 1*len(num[j:])
            if leng[num[j]] < temp:
                leng[num[j]] = temp
        
        if num[j] not in cnt:
            cnt[num[j]] = 1
        else:
            cnt[num[j]] += 1

        if num[j] not in dic:
            dic[num[j]] = -1

        if num[j] not in alpha:
            alpha.append(num[j])


alpha = sorted(alpha, key=lambda x:(leng[x],cnt[x]))
result = 9
while alpha:
    target = alpha.pop()
    dic[target] = result
    result -= 1

for i in answer:
    temp=""
    for j in i:
        temp+=str(dic[j])
    final_answer.append(int(temp))

print(sum(final_answer))

정답 풀이과정

1. '가장 높은 자릿 수와, 그가 같을 경우 몇번 나왔는지' 를 정렬기준으로 사용하고자 한 것이 원인이었다.

2. 따라서 알파벳을 발견 할때 마다. pow(10,자릿수)를 하여 cnt에 저장하였고 이를 정렬기준으로 사용하였다.

정답 코드

from math import pow
n = int(input())
cnt={}
dic={}
alpha=[]
answer=[]
final_answer=[]
for i in range(n):
    num = input()
    answer.append(num)
    for j in range(len(num)):
        temp = 1*len(num[j:])-1
        if num[j] not in cnt:
            cnt[num[j]] = pow(10,temp)
        else:
            cnt[num[j]] += pow(10,temp)

        if num[j] not in dic:
            dic[num[j]] = -1

        if num[j] not in alpha:
            alpha.append(num[j])


alpha = sorted(alpha, key=lambda x: cnt[x])
result = 9
while alpha:
    target = alpha.pop()
    dic[target] = result
    result -= 1

for i in answer:
    temp=""
    for j in i:
        temp+=str(dic[j])
    final_answer.append(int(temp))

print(sum(final_answer))