파이썬 백준 알고리즘: 문자열 덧셈 1339

안녕하세요! 개발자 여러분들을 위한 "파이썬 백준 알고리즘" 포스트입니다. 이번에는 알파벳을 숫자로 대체하여 문자열의 합을 계산하는 문제를 다루어 보려고 합니다. 주어진 코드를 통해 문제를 이해하고, 효과적인 풀이 방법을 알아보겠습니다.

문제 내용

주어진 코드는 N개의 단어를 입력받고, 각 단어의 알파벳을 숫자로 대체하여 문자열의 합을 계산하는 로직입니다. 입력으로 주어진 단어의 개수(N)와 각 단어를 리스트(words)에 저장한 후, 각 알파벳에 대해 가중치를 부여하여 합(sum_number)을 계산합니다.

문제 이해하기

이 문제는 주어진 단어의 알파벳을 숫자로 대체하여 문자열의 합을 계산하는 것입니다. 각 알파벳은 자릿수에 따라 가중치를 가지며, 가장 큰 가중치를 가진 알파벳부터 큰 수로 대체합니다. 가장 큰 가중치를 가진 알파벳은 9로 대체하고, 그 다음은 8, 7, ..., 1로 대체합니다. 예를 들어, "ABC"라는 단어가 주어졌을 때, A는 9로, B는 8로, C는 7로 대체하여 숫자 987를 얻습니다. 이렇게 대체된 숫자들을 모두 합산하여 최종 결과값을 구합니다.

풀이 코드

pythonCopy code
import sys
from collections import defaultdict

input = sys.stdin.readline

words = []
alphabet_sum_dict = defaultdict(int)

N = int(input())
for _ in range(N):
    word = input().strip()
    words.append(word)

    word_length = len(word)
    for index, alphabet in enumerate(word):
        alphabet_sum_dict[alphabet] += pow(10, word_length - index - 1)

sum_number = 0
remain_number = 9
for key, value in sorted(alphabet_sum_dict.items(), reverse=True, key=lambda item: item[1]):
    sum_number += value * remain_number
    remain_number -= 1

print(sum_number)

풀이 방법

1. 단어들을 입력받아 리스트(words)에 저장합니다.
2. 각 단어마다 알파벳의 가중치를 계산하여 alphabet_sum_dict 딕셔너리에 저장합니다.
   • 딕셔너리의 키(key)는 알파벳, 값(value)은 가중치입니다.
   • 가중치는 pow(10, word_length - index - 1)로 계산됩니다. (index는 알파벳의 인덱스, word_length는 단어의 길이)
   • 예를 들어 "ABC"라는 단어가 주어졌을 때, A는 100, B는 10, C는 1의 가중치를 갖게 됩니다.
3. alphabet_sum_dict를 가중치(value)를 기준으로 내림차순으로 정렬합니다.
4. 정렬된 순서대로 가중치(value)에 남은 숫자(remain_number)를 곱하고, sum_number에 더해줍니다.
   • remain_number는 9부터 시작하여 1씩 감소합니다.
   • 가장 큰 가중치를 가진 알파벳은 9로 대체되고, 그 다음은 8, 7, ..., 1로 대체됩니다.
5. 최종적으로 sum_number를 출력합니다.

시간 복잡도

주어진 단어의 개수를 N이라고 할 때, 단어를 입력받는 부분의 시간 복잡도는 O(N)입니다. 이후 단어들을 처리하고 가중치를 계산하는 부분의 시간 복잡도는 O(N * L)입니다. (L은 단어의 평균 길이) 딕셔너리를 가중치에 따라 정렬하는 부분의 시간 복잡도는 O(K log K)입니다. (K는 알파벳의 개수) 따라서 전체 시간 복잡도는 O(N * L + K log K)입니다.

 

 

혹시 문제가 잘 안풀리고 답답하신가요? 아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요! 이것만 알아도 네카라뿌십니다~

 

👉 백준 알ㅂ고리즘 모음