백준 1339 - 파이썬

https://www.acmicpc.net/problem/1339

1339번: 단어 수학

문제풀이

이 문제를 보고 바로 생각 난 알고리즘 과정은 다음과 같다.

 

1. 입력된 값 중 문자열이 제일 긴 문자열 구하기

2. 맨 앞부터 순서대로 알파벳에 혀재 입력 가능한 숫자 중 가장 큰 숫자 지정

3. 최대 길이가 8이기 때문에 순서대로 남은 숫자 부여

4. 알파벳 숫자로 치환 후 합하기

 

그리고 여기서 숫자는 어떻게 추출할지 고민하다가 큐 자료구조를 이용하여 가장 큰 숫자부터 출력하면 좋겠다는 생각을 했다.

 

위 알고리즘을 갖고 문제를 풀어 나가던 도중 문제점 하나를 찾았다. 굳이 일의 자리 숫자가 백의 자리 숫자보다 클 필요는 없다는 점이다. 그래서 아래와 같이 알고리즘을 수정해 보았다.

 

1. 문자열 길이가 더 긴 문자부터 차례대로 숫자 지정

2. 길이가 그 다음 긴 문자열부터 차례대로 번갈아가며 지정

 

접근하는 방식은 좋았으나 결국 이 문제는 스스로 풀지 못하고 다른 사람의 풀이를 보았다.

 

import sys

n = int(sys.stdin.readline())

alpha = []
alpha_dict = {}
numList = []

for i in range(n):
  alpha.append(sys.stdin.readline().rstrip())

for i in range(n):
  for j in range(len(alpha[i])):
    if alpha[i][j] in alpha_dict:
      alpha_dict[alpha[i][j]] += 10 ** (len(alpha[i])-j-1)
    else:
      alpha_dict[alpha[i][j]] = 10 ** (len(alpha[i])-j-1)

for val in alpha_dict.values():
  numList.append(val)

numList.sort(reverse=True)

sum=0
pows=9
for i in numList:
  sum += pows * i
  pows -= 1

print(sum)

이 코드에서의 핵심은 다음 코드들이다

if alpha[i][j] in alpha_dict:
   alpha_dict[alpha[i][j]] += 10 ** (len(alpha[i])-j-1)
else:
   alpha_dict[alpha[i][j]] = 10 ** (len(alpha[i])-j-1)

이 코드는 단어의 알파벳이 이미 딕셔너리에 존재하면 원래 값에다가 현재 자리에 맞게 추가하는 것이고, 존재하지 않으면 새롭게 딕셔너리에 추가하는 코드이다. 이렇게 한 이유는 다음과 같다.

pows = 9
for i in numList:
    sum += pows * i
    pows -= 1

입력값이 aaa, abc인 경우 딕셔너리에는 {'a': 211, 'b': 10, 'c': 1} 이렇게 저장이 된다. a가 211인 이유는 백의 자리인 a가 2번 나오고 10의 자리 한번 1의 자리 1번 이렇게 나왔기 때문이다. a의 값이 가장 큰 부분을 차지하기 때문에 9부터 순서대로 곱해주면 답을 구할 수 있다.

 

이 문제를 풀면서 얻어가는 점은 자릿수마다 알파벳이 나온 횟수를 저장하여 거기다가 9부터 차례대로 숫자를 곱한 후 더했다는 점이다. 이런식의 사고를 한번 바꿔보는 식의 생각을 못 한 점이 아쉽고, 이러한 방법으로도 풀 수 있다는 것을 알았으니 이러한 방식을 적용하여 풀어야 하는 문제가 있으면 적용해서 풀어봐야 되겠다.