[백준 1339] - 단어 수학 Python

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

 

 

문제 전략

이 문제는 여러 개의 단어로 이루어진 알파벳들에 0~9까지의 숫자를 부여하여, 그 단어들의 합을 최대로 만드는 문제입니다.

핵심은 어떤 알파벳에 9를 부여할 것인지 결정하는 기준을 세우는 것입니다. 따라서 우리는 다음과 같은 '가중치 합산' 전략을 사용합니다.

 

추상화된 흐름

 

1. 가중치 수치화: 각 단어를 훑으며 포함된 알파벳이 전체 합에 기여하는 '자릿수 값'을 계산한다. (예: ABC에서 A는 100, B는 10, C는 1)
2. 데이터 통합: 여러 단어에 등장하는 같은 알파벳들의 가중치를 모두 합산하여 하나의 리스트나 딕셔너리에 저장한다.
3. 그리디 적용: 합산된 가중치를 내림차순 정렬하여, 가장 큰 값을 가진 알파벳부터 9, 8, 7... 순으로 숫자를 배정한다.
4. 시간 복잡도: 단어의 개수가 N, 최대 길이가 L일 때 가중치 계산에 O(N \times L), 정렬에 O(26 \log 26)이 소요되어 매우 효율적으로 해결 가능하다.

 

해결 과정

 

• 입력값 처리: sys.stdin.readline을 사용하여 단어들을 입력받고, strip()으로 개행 문자를 제거한다.
• 가중치 리스트 초기화: 알파벳 26개에 대응하는 weight = [0] * 26 리스트를 생성한다.
• 자릿수 계산: * 각 단어(word)를 돌며 각 글자(word[i])의 위치를 파악한다.
  • 해당 글자의 가중치를 10 ** (len(word) - 1 - i)로 계산하여 weight[ord(word[i]) - 65]에 더해준다(+=).
• 최종 합산:
  • weight 리스트를 내림차순 정렬한다.
  • 9부터 1씩 줄여가며 가중치와 곱한 값을 result 변수에 누적한다.

 

어려웠던 점 및 복기

• 시행착오: 처음에는 무조건 단어의 길이가 길거나 앞자리에 있는 알파벳에 큰 수를 주려 했으나, 낮은 자릿수라도 여러 번 등장하면 더 큰 영향력을 가질 수 있다는 것을 깨달았다.
• 핵심 포인트: 그리디 문제의 핵심은 '가장 욕심을 부려야 할 기준'을 찾는 것인데, 이 문제에서는 그 기준이 단순 위치가 아닌 '수학적 가중치의 합'임을 이해하는 것이 가장 중요했다.
• 복기: 알파벳이 최대 10개뿐이라 브루트포스도 가능하겠지만, 가중치 모델을 세워 그리디로 푸는 것이 훨씬 직관적이고 확장성 있는 풀이였다.

 

전체 코드