백준 1339 파이썬

 

1339번: 단어 수학

 

문제 풀이의 핵심

1. 딕셔너리 사용 ex) {'G': 9, 'C': 8, ,,,,,}
2. 가중치를 주어서 우선순위 매기기

내가 문제를 풀다가 놓친 부분은 가중치를 계산 하는 부분이었다. 가중치를 계산할 때 고려해야할 부분은 2가지가 있는데,

- 자릿수가 큰 것뿐만이 아니라

- 알파벳이 나온 빈도수

자릿 수가 작긴 하지만 빈도 수가 많다면, 이 수를 큰 수로 매칭하는 것이!  그저 자릿수가 큰 수를 큰 수로 매칭했을 때 보다 결과 값이 클 수도  있다.

예시를 들자면, 아래와 같은 입력에서 답은 1772가 나와야한다. A가 9가 아닌, B가 9일 때 결과 값이 크게 나온다.

10
ABB
BC
BC
BC
BC
BC
BC
BC
BC
BC

=>  따라서 가중치를 계산할 때는 빈도수와 자릿수 모두 생각해서 가중치에 포함시켜 계산해야한다.

코드

n = int(input())
dic = {} # {'G':9,,,,,}
num = [] # 가중치 계산 값을 저장할 리스트
for _ in range(n): # 입력 및 가중치 계산
    arr = list(input())
    for i in range(len(arr)):
        a = len(arr) - i - 1
        if arr[i] not in dic:
            dic[arr[i]] = 10 ** a
        else: # 이미 딕셔너리에 존재한다면, 자릿수를 계속 더하여 가중치를 증가시킨다(여러번 나올 수록 커짐)
            dic[arr[i]] += 10 ** a

# value 값인 가중치만 뽑아서 내림차순 정렬
for i in dic.values():
    num.append(i)
num.sort(reverse=True)

# 내림 차순 정렬한 값 * 9 부터 차례대로 곱한다. 
res = 0
temp = 9
for v in num:
    res += (temp * v)
    temp -= 1
print(res)

 

참고

[백준] 1339 단어 수학 (Python 파이썬)