1307. Verbal Arithmetic Puzzle

[zeikar]

Problem link

https://leetcode.com/problems/verbal-arithmetic-puzzle/

Problem Summary

문자로 이루어진 방정식이 있을 때 문자에 숫자를 적당히 대입해 식이 성립하는지 판단하는 문제.

Solution

처음에 간단한 완전탐색 문제인줄 알고 풀었는데 예시부터 시간 초과가 뜸...
생각보다 꽤 빡센 완전탐색 문제.

일단 전체적인 코드는 아래 디스커션 참고함.
https://leetcode.com/problems/verbal-arithmetic-puzzle/discuss/1484528/Python.-Permutations!-No-backtracking

먼저 완전 탐색을 돌릴 문자를 구해야 한다. 여기서 맵(카운터)를 쓸 수 있는데 나중에 계산을 빠르게 하기 위해 자리수의 합을 저장해둔다.
즉, SEND의 경우 S: 1000, E: 100, N: 10, D:1 로 하고, 다른 문자가 나오면 여기에 더해주면 된다. 반대로 result는 음수로 더해준다.

그러면 예시 1번의 카운터는 아래와 같은 모양이 된다.

Counter({'S': 1000, 'E': 91, 'R': 10, 'D': 1, 'Y': -1, 'N': -90, 'O': -900, 'M': -9000})

여기에서 permutations로 다 돌아도 되겠지만 시간 초과가 될 것이므로... 음수, 양수를 나누는 방법을 사용해야 한다. 어떻게 보면 일종의 meet in the middle 느낌.

양수로 만들 수 있는 모든 합을 구해둔 후 음수로 만들 수 있는 모든 합을 구해서 서로 반대가 되었을 때 만드는 자리수가 겹치지 않으면 정답이다.
이게 아래 permutations for문 두 개에서 하는 일이고, 맨 처음이 0으로 시작하면 안되므로 거르기 위해 non_leading_zero 를 사용했다.

Source Code

from collections import Counter, defaultdict
from itertools import permutations
from typing import List


class Solution:
    def isSolvable(self, words: List[str], result: str) -> bool:
        c = Counter()
        non_leading_zero = set()
        for word in words:
            if len(word) > 1:
                non_leading_zero.add(word[0])
            for i in range(len(word)):
                c[word[i]] += 10 ** (len(word) - i - 1)

        if len(result) > 1:
            non_leading_zero.add(result[0])
        for i in range(len(result)):
            c[result[i]] -= 10 ** (len(result) - i - 1)

        pos = []
        neg = []
        for l, v in c.items():
            if v > 0:
                pos.append((l, v))
            elif v < 0:
                neg.append((l, -v))

        if len(pos) > len(neg):
            neg, pos = pos, neg

        sum_map = defaultdict(list)
        for permu in permutations(list(range(10)), len(pos)):
            if 0 in permu and pos[permu.index(0)][0] in non_leading_zero:
                continue

            s = 0
            idx = 0
            for (l, v) in pos:
                s += v * permu[idx]
                idx += 1
            sum_map[s].append(set(permu))

        for permu in permutations(list(range(10)), len(neg)):
            if 0 in permu and neg[permu.index(0)][0] in non_leading_zero:
                continue

            s = 0
            idx = 0
            for (l, v) in neg:
                s += v * permu[idx]
                idx += 1

            if s in sum_map:
                for s2 in sum_map[s]:
                    if not set(permu) & s2:
                        return True

        return False