[백준] 1339 : 단어 수학 (파이썬)

그리디, 백트래킹 문제

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

---

접근 방식 

그리디 

알파벳이 각각의 자릿수에 몇번 등장하는지를 자릿수 별로 10의 거듭제곱 승의 가중치를 부여하여 알파벳 dictionary에 기록

-> 가중치 값이 가장 큰 알파벳 순서대로 9 ~ x 까지의 숫자를 부여한 후 결과값 출력

백트래킹

9 ~ x (각기 다른 알파벳의 갯수만큼)의 수를 순열로 배치 -> 합했을 때에 가장 큰 결과값이 나올 때의 값을 기록

---

짚고 넘어갈 Point

✏️ 백트래킹 전에는 시간 복잡도 계산을 하자 !

순열 

주어진 n개의 원소 중에서 r개를 선택하여 배열하는 경우의 수

조합 

순서를 고려하지 않고 주어진 n개의 원소 중에서 r개를 선택하는 경우의 수

 

✏️ Dictionary에서 key값이 아닌 key의 index(몇번째 key인지) 활용해서 value에 접근하는 법

list로 key 값을 추출하여 접근

my_dict = {'a': 1, 'b': 2, 'c': 3}

# key 값을 리스트로 변환 후 index로 접근
keys = list(my_dict.keys())
value = my_dict[keys[1]]  # 두 번째 key ('b')에 접근
print(value)  # 출력: 2

---

💡 풀이코드 (Python3 성공 - 그리디)

import sys 
import heapq

n = int(sys.stdin.readline())
arr = []
dic = {}
alpha = {}
heap = []
ans = 0

for _ in range(n):
    a = sys.stdin.readline().strip()
    arr.append(a)
    for cnt, s in enumerate(a):
        if s not in dic:
            dic[s] = 10 ** (len(a) - cnt - 1)
        else:
            dic[s] += 10 ** (len(a) - cnt - 1)
    

dic = dict(sorted(dic.items(), reverse=True, key=lambda x:x[1]))

num = 9
for k, v in dic.items():
    dic[k] = num 
    num -= 1

for i in arr:
    tmp = 0
    for cnt, j in enumerate(i):
        tmp += dic[j] * (10 ** (len(i) - cnt - 1))
    ans += tmp


print(ans)

 

풀이 방식

입력이 다음과 같다고 하자.

 cabb
      bd
      be
      bb
      bb
      bb
      bb

 

무조건적으로 높은 자리의 알파벳에 큰 숫자를 배치하면 안된다.

위와 같은 경우처럼, 특정 알파벳이 반복적으로 나오는 경우에는 그 순위가 역전될 수도 있기 때문이다.

 

따라서, 입력받은 모든 알파벳 문자열을 순회하며, 각 알파벳이 몇번째 자릿수에 몇번 등장했는지의 여부를 dictionary에 기록해준다.

 

그 후, dictionary를 내림차순으로 정렬한 후 등장하는 알파벳을 가장 큰 수인 9부터 차례대로 대입해준다.

---

💡 풀이코드 (PyPy3 실패 - 백트래킹)

import sys 
# sys.setrecursionlimit(1000) # 메모리 초과 (너무 많이 할당하면 메모리 초과 남)
global ans, alphaSet, alpha
n = int(sys.stdin.readline())
arr = []
alpha = {}
ans = 0
alphaSet = set()

for _ in range(n):
    a = sys.stdin.readline().strip()
    arr.append(a)
    for s in a:
        alpha[s] = 0
        alphaSet.add(s)

# print(alpha)
alphaSet = list(alphaSet)
checked = [False for _ in range(10)]


# 알파벳 - 숫자 연결
def findMax():
    global ans, alpha 

    tmpAns = 0
    for i in arr:
        tmp = 0
        for ii, s in enumerate(i):
            tmp = tmp * 10 + alpha[s]
            # tmp += alpha[s] * (10 ** (len(i) - ii - 1))
        tmpAns += tmp 
    ans = max(tmpAns, ans)
    
def dfs(idx):
    if idx == len(alpha):
        findMax()
        return
    
    for i in range(9, 9 - len(alpha), -1):
        if checked[i] == False: 
            checked[i] = True 
            alpha[alphaSet[idx]] = i 
            dfs(idx + 1)
            checked[i] = False 
            alpha[alphaSet[idx]] = 0

dfs(0)
print(ans)

시간 복잡도

1. findMax()

총 입력 받는 문자열의 갯수 = n, 각 문자열의 길이 = k라 할 때, 

시간복잡도 = O(n⋅k)

 

2. dfs(idx)

백트래킹을 사용하여 모든 알파벳에 숫자를 할당하는 순열의 형태

서로 다른 알파벳의 갯수 즉, alphaSet의 길이를 m이라 할 때, 순열의 수는 P(10,m) = 10개의 숫자 중 m개를 순서대로 선택

 

P(10, m) = 10! / (10-m)!

 

-> 전체 시간 복잡도

O(P(10,m)⋅n⋅k)

 

최악의 시간 복잡도

1. findMax()에서의 연산

• 각 단어가 길이 k=8이고, 단어의 개수가 N=10이므로, 숫자 변환에 필요한 시간은 O(n⋅k)=O(10⋅8)=O(80)이다.
• findMax()는 P(10,10)=3,628,800번 호출된다.

2. 전체 시간복잡도

• 전체 시간은 P(10,10)⋅n⋅k에 비례한다.

최악의 경우 계산 시간=3,628,800⋅10⋅8=290,304,000=290,304,000

즉, 약 2억 9천만 번의 연산이 필요하다.

​

---

💡 풀이코드 (PyPy3 성공 - 백트래킹)

def backtracking(index, word, alphabet_list, value, visited, n):
    global max_sum
    if index == len(alphabet_list):
        # 모든 알파벳에 숫자가 할당된 경우, 합을 계산
        total_sum = 0
        for w in word:
            num = 0
            for char in w:
                num = num * 10 + value[alphabet_list.index(char)]
            total_sum += num
        max_sum = max(max_sum, total_sum)
        return
    
    # 가능한 숫자들 (0~9) 중에서 할당해보는 백트래킹
    for i in range(10):
        if not visited[i]:
            visited[i] = True
            value[index] = i
            backtracking(index + 1, word, alphabet_list, value, visited, n)
            visited[i] = False
            value[index] = 0

def main():
    global max_sum
    n = int(input())  # 단어의 개수
    word = [input().strip() for _ in range(n)]  # 단어들 입력 받기
    
    alphabet_list = []
    for w in word:
        for char in w:
            if char not in alphabet_list:
                alphabet_list.append(char)  # 알파벳이 alphabet_list에 없으면 추가
    
    visited = [False] * 10  # 숫자 0~9 사용 여부
    value = [0] * len(alphabet_list)  # 각 알파벳에 대응하는 숫자 저장
    max_sum = -float('inf')  # 최대값 초기화
    
    backtracking(0, word, alphabet_list, value, visited, n)
    
    print(max_sum)

if __name__ == "__main__":
    main()