백준(Baekjoon Online Judge) - 1339번(단어 수학) 문제 풀이

1. 문제

2. 입출력 예시

3. 문제 풀이

이 문제는 딕셔너리를 활용하면 어렵지 않게 해결할 수 있다. 각 단어의 알파벳을 key로 설정 후 알파벳의 위치를 10의 제곱으로 나타내기로 하였다. 이를 표로 나타내면 아래와 같다.

위 표에 나타난 단어의 알파벳을 중복제거 후 값이 큰 순으로 정렬하면 아래와 같다. 이 알파벳 정렬 순으로 반복을 수행하며 알파벳에 해당하는 값에 9 - 인덱스 값의 총 합이 이 문제의 답이 된다.

문제를 해결하기 위해 먼저 아래와 같이 처리 순서를 세워보았다.

• 입력할 단어의 수량(N)을 입력받고, 단어를 저장할 리스트(words)를 생성한다.
• 입력할 단어의 수량만큼 반복하며 단어를 입력받아 리스트에 추가한다.
• 알파벳 정보를 저장할 딕셔너리(index)를 생성 후 반복문을 통해 리스트에 저장된 단어를 호출한다. 단어의 인덱스가 클 수록 10의 제곱 단위가 커지며 이를 10의 제곱으로 나타내기 위하여 단어의 길이를 변수(length)에 저장 후 아래의 내용을 수행한다.
  • 이중반복문을 사용하여 단어의 알파벳 만큼 반복한다. 만약 딕셔너리의 key에 해당 알파벳이 포함되어 있을 경우에는 해당 key의 value에 10의 length 제곱을 더하며(위의 표에서 C의 경우(1010)가 이에 해당한다.), 그렇지 않을 경우에는 딕셔너리에 key와 value를 해당 알파벳과 10의 length 제곱으로 초기화한다.
  • 이중반복문의 반복이 진행될 때마다 단어에 해당하는 알파벳의 자릿수가 뒤로 밀려나므로 length에 1을 뺀다.
• 반복이 종료된 후에는 딕셔너리의 value를 리스트(numbers)로 저장하고, 이를 내림차순으로 정렬한다.
• 결과값(total)을 0으로, 적용할 숫자(cnt)를 9로 초기화한 후 정렬한 리스트(numbers) 만큼 반복을 수행한다. 반복을 수행하는 동안 결과값에 해당 알파벳의 값 × 적용할 숫자를 더하고, 적용할 숫자에 1을 뺀다.
• 반복이 종료되면 결과값을 출력한다.

이를 코드로 나타내면 아래와 같으며, 메모리는28,776 KB, 시간은 68 ms가 소요되었다.

import sys

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

words = []

for _ in range(N):
    words.append(sys.stdin.readline().replace("\n", ""))

index = {}

for word in words:
    length = len(word) - 1
    for c in word:
        if c in index:
            index[c] += 10 ** length
        else:
            index[c] = 10 ** length
        length -= 1

numbers = sorted(index.values(), key=lambda x: -x)

total = 0
cnt = 9

for number in numbers:
    total += (number * cnt)
    cnt -= 1

print(total)

참고자료

• 백준알고리즘 문제 - 1339번 단어 수학