[백준] 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=이고, 단어의 개수가 N=이므로, 숫자 변환에 필요한 시간은 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()