BOJ 백준 1339: 단어 수학

Table of contents

들어가며

걸린 시간: 90분 (자력으로 풀지 못함)

사실 처음에 읽고, BOJ 백준 2529: 부등호가 생각이 났습니다.
그 문제는 그래도 경우의 수 pruning을 해서, backtracking으로 풀 수라도 있지, 이거는 완전 탐색이더라고요. (물론 나중에 태그까고 그리디라는 걸 알게됐지만요…)

접근

모든 단어에 포함된 알파벳 종류가 최대 10개이고, 숫자도 0부터9까지이니, 최대 경우의 수는 10!(대충 300만) 그리고 그 각 경우의 수 안에서 숫자로 변환해서 더하는 경우의 수라 해봤자 대략 80…
이러면 절대로 시간 안에 안 걸리겠는데? 하고 접근을 해봤습니다.

구현

import sys
from itertools import permutations
input = sys.stdin.readline

def calc():
    summation = 0
    for s in stringList:
        len_s = len(s)
        num = 0
        factor = 1
        for i in range(len_s - 1, -1, -1):
            num += mappingTable[ord(s[i]) - ord('A')] * factor
            factor *= 10
        summation += num
    return summation

def DFS(level, cur_digit):
    if level == numAlphabets - 1:
        global ans
        tmp_ans = calc()
        # print(tmp_ans)
        ans = max(ans, tmp_ans)
        return

    for i in range(10):
        if isUsed[i]:
            continue
        isUsed[i] = True
        mappingTable[ord(alphabetList[level + 1]) - ord('A')] = i
        DFS(level + 1, i)
        isUsed[i] = False

if __name__ == "__main__":
    N = int(input().strip())
    stringList = [input().strip() for _ in range(N)]
    alphabetSet = set()
    ans = 0
    for string in stringList:
        for ch in string:
            alphabetSet.add(ch)

    # 0 -> alphabet0, 1 -> alphabet1
    alphabetList = list(sorted(alphabetSet))
    numAlphabets = len(alphabetList)
    isUsed = [False for _ in range(10)]
    # alphabet0 -> digit0, ...
    mappingTable = [-1 for _ in range(26)]
    permutationCandsGen = permutations(range(10), numAlphabets)
    for permutationCand in permutationCandsGen:
        for idx, digit in enumerate(permutationCand):
            mappingTable[ord(alphabetList[idx]) - ord('A')] = digit
        ans = max(ans, calc())
    # for i in range(10):
    #     isUsed[i] = True
    #     mappingTable[ord(alphabetList[0]) - ord('A')] = i
    #     DFS(0, i)
    #     isUsed[i] = False
    print(ans)

코드를 보시면 알겠지만, 일단 DFS로 순열을 만들어도 통과가 되고, permutations library를 써도 통과가 됩니다. (단, pypy3 기준, python3는 안됩니다 ㅠ)
일단 dictionary와 같은 HashMap 자료구조로 어떤 알파벳이 어떤 숫자에 대응되는지 구현하면 안됩니다.
같은 O(1)이어도 List Indexing으로 구현하는 것이 훨씬 더 빠릅니다. (왜냐면 Hashing 알고리즘 + Probing 자체가 조금 더 많은 연산을 요하기 때문). 그리고 calc 함수를 보면, ** 연산자 대신 직접 for 내에서 자릿수마다 곱하기 10제곱수를 하여 직접 계산을 했는데, 이 또한 일정 부분의 시간 복잡도 개선을 하게 됩니다.
물론 HashMap 자료구조를 List Indexing으로 바꾼 게 TLE를 받냐 마느냐를 가르게 합니다.
같은 시간 복잡도라도 자료구조의 특징에 따라 최적화를 할 수 있으니, 항상 생각을 합시다!! 아 그리고 이 문제의 태그는 그리디여서 그리디로 풀 수 있습니다!