[그리디] 코딩테스트 문제 TIL (단어 수학) - 백준 1339번

말하는 감자·2024년 12월 19일

TIL algorithm baekjoon greedy python sorting 그리디 백준 알고리즘 정렬 코딩테스트 코딩테스트 준비 파이썬

코딩테스트 유형별 풀이

목록 보기

41/67

1. 오늘의 학습 키워드

그리디 알고리즘

2. 문제: 1339. 단어 수학

단계: 🥇 골드 4단계
주제:
- 그리디 알고리즘
출처: https://www.acmicpc.net/problem/1339

문제

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

예제 입력 1 복사

2
AAA
AAA

예제 출력 1 복사

예제 입력 2 복사

2
GCF
ACDEB

예제 출력 2 복사

예제 입력 3 복사

10
A
B
C
D
E
F
G
H
I
J

예제 출력 3 복사

예제 입력 4 복사

2
AB
BA

예제 출력 4 복사

3. 문제 풀이

Step1. 문제 이해하기

주어진 단어는 알파벳 대문자로만 이루어져 있으며, 알파벳을 숫자로 바꾸어 계산합니다.
같은 알파벳은 동일한 숫자로 변환해야 하고, 서로 다른 알파벳은 서로 다른 숫자로 변환해야 합니다.
숫자는 0부터 9까지 사용할 수 있으며, 알파벳에 높은 숫자를 배정해야 합을 최대화 할 수 있습니다.

입출력을 살펴 보겠습니다.

Input:
- 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어집니다.
  - 시간 복잡도 상으로 충분히 여유가 있을것으로 예상 됩니다.
- 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어집니다. 알파벳은 대문자로만 이루어져 있습니다.
Output:
- 주어진 단어의 합의 최댓값을 출력합니다.

Step2. 문제 분석하기

주어진 단어들의 합이 최대가 될려면 어떻게 해야 할까요?

자릿수가 가장 높은 위치에 있는 알파벳에 가장 큰 숫자 9를 넣으면 되지 않을까요?

문제에서 예시가 있습니다.

GCF + ACDEB를 보시면 A = 9, C = 8, …을 지정하는 것을 볼 수 있습니다.

가장 높은 자릿수의 숫자가 커야 가장 큰 수를 가질 수 있기 때문에 각 알파벳의 자릿수를 기준으로 정렬을 하면 될 것 같습니다.

Step3. 코드 설계

알파벳 가중치 계산:
- 각 알파벳이 단어에서 차지하는 중요도를 계산합니다.
- 중요도는 자릿수에 따라 달라지며, 각 알파벳에 대해 해당 자릿수의 가중치를 누적합니다.
  - 예: GCF에서 G는 100의 가중치, C는 10의 가중치, F는 1의 가중치를 가집니다.
- 이를 통해 각 알파벳의 기여도를 계산할 수 있습니다.
알파벳 정렬:
- 계산된 가중치를 기준으로 내림차순 정렬합니다.
- 중요도가 높은 알파벳에 높은 숫자를 배정합니다.
숫자 배정 및 합산:
- 가중치가 높은 알파벳부터 9, 8, 7, ..., 0의 숫자를 차례로 배정합니다.
- 각 단어를 숫자로 변환하여 합산합니다.

Step4. 코드 구현

import sys
N = int(sys.stdin.readline().strip())
words = [sys.stdin.readline().strip() for _ in range(N)]

weights = {}
for word in words:
    length = len(word)
    for i, char in enumerate(word):
        power = 10 ** (length - i -1)
        if char in weights:
            weights[char] += power
        else:
            weights[char] = power
weights = sorted(weights.items(), key=lambda x:x[1], reverse=True)

assign_numbers = {}
num = 9
for char, _ in weights:
    assign_numbers[char] = num
    num -= 1

total = 0
for word in words:
    num_value = 0
    for char in word:
        num_value = 10 * num_value + assign_numbers[char]
    total += num_value
print(total)

코드 설명:
- 가중치 계산:
  - 각 알파벳의 가중치를 계산하여 딕셔너리에 저장합니다.
  - 자릿수에 따라 가중치를 부여하며, 같은 알파벳이 여러 단어에 등장하면 가중치를 누적합니다.
- 정렬 및 숫자 배정:
  - 가중치를 기준으로 내림차순 정렬하여 높은 가중치를 가진 알파벳부터 숫자를 배정합니다.
- 숫자 변환 및 합산:
  - 각 단어를 숫자로 변환하고, 이를 합산하여 결과를 출력합니다.
시간 복잡도:
1. 가중치 계산:
  - 단어의 길이를 L, 단어의 개수를 N이라고 하면 O(N \cdot L)입니다.
2. 정렬:
  - 알파벳의 개수는 최대 10개이므로 $O(10 \log 10)$ , 즉 상수 시간입니다.
3. 숫자 변환 및 합산:
  - $O(N \cdot L)$ .
  
  총 시간 복잡도: $O(N \cdot L)$ 이며, $N \leq 10$ , $L \leq 8$ 이므로 매우 효율적입니다.
결과: