[백준 1339] 단어 수학

문제
단어 수학 문제는 N개의 단어로 이루어져 있으며 각 단어는 알파벳 대문자로만 이루어져있다.
이때 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합한다. 이때 합이 최대가 되도록 만들어라.

입력
첫째 줄에 단어의 개수 N이 주어진다.
둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다.
입력된 모든 단어에 포함되어 있는 알파벳은 최대 10개이며 수의 최대 길이는 8이다.

출력
첫째 줄에 최대값을 출력한다.

---

접근

처음에 접근했던 방식은 문자열의 길이가 큰 것의 앞자리부터 숫자를 매기는 것이었다. 하지만 어떻게 구현을 해야할지 감이 잡히지 않았다 그래서 구글링을 해본 결과 아래의 풀이가 흥미로웠다.

suri78.tistory.com/183

[백준알고리즘] 1339번: 단어 수학 -Python

 

입력을 받을 때 알파벳을 정수형을 바꾸고 -65를 한다. 그렇다면 A가 0이 되는데 이를 26개의 0으로 초기화된 리스트의 인덱스로 활용한다. 즉 A는 0번째 B는 1번째에 해당된다.

그리고 ABC라는 문자열이 있을 때 이를 숫자로 나타내기위해 A에 10의 제곱, B에 10의 1제곱, C에 10의 0제곱을 하면 A는 백의자리 B는 십의자리 C는 일의자리에 있다는 것을 표현하게 된다. 입력받은 문자열을 이런식으로 표현하여 길이가 26인 리스트의 알파벳 자리에 더해준다.

만약 C가 1의자리에 2번 10의자리에 2번이면 C에 해당되는 인덱스에 22가 들어있게된다.

 

이제 이를 활용하여 리스트를 오름차순으로 정렬하여 9부터 0까지 처음부터 곱하게 된다.

만약 C가 3이라면 위에서 22가 있었기 때문에 곱하면 66을 최종해에 더해주게된다.

 

정리를 하면 각 알파벳이 몇의 자리에 몇 번 나왔는지 검사하여 가장 높은 수에 해당되는 알파벳부터 9~0을 곱하고 이를 모두 더하면 최대합이 되는 것이다.

 

구현

N개의 문자를 입력받을 때 숫자로 변형하고 65를 빼준 값을 리스트에 저장한다.

그리고 0으로 초기화하고 26의 길이를 갖는 alpha_count를 선언하여 알파벳들이 몇의 자리에 몇 번나오는지 기록한다.

N = int(input())
matrix = [list(map(lambda x: ord(x)-65, input())) for _ in range(N)]
alpha_count = [0 for _ in range(26)]

 

N개의 문자열을 검사하며 각 문자열의 뒤에서부터 10의 0제곱에서 증가시켜 각각 결과를 해당 알파벳의 인덱스에 더한다.

for y in range(N):
    k = 0
    for x in range(len(matrix[y])-1, -1, -1):
        alpha_count[matrix[y][x]] += (10**k)
        k += 1

 

오름차순으로 정렬 후에 9~0을 순서대로 곱하여 더해주도록 한다.

최종적으로 모든 문자열을 숫자로 매핑했을 때의 최대합이 된다.

alpha_count.sort(reverse=True)
answer = 0
number = 9
for idx in range(26):
    if alpha_count[idx] == 0:
        break
    answer += (number * alpha_count[idx])
    number -= 1

print(answer)

---

전체 코드

N = int(input())
matrix = [list(map(lambda x: ord(x)-65, input())) for _ in range(N)]
alpha_count = [0 for _ in range(26)]

for y in range(N):
    k = 0
    for x in range(len(matrix[y])-1, -1, -1):
        alpha_count[matrix[y][x]] += (10**k)
        k += 1

alpha_count.sort(reverse=True)
answer = 0
number = 9
for idx in range(26):
    if alpha_count[idx] == 0:
        break
    answer += (number * alpha_count[idx])
    number -= 1

print(answer)