[BOJ/PYTHON] 15811. 복면산?!

백준 문제 링크: https://www.acmicpc.net/problem/15811

문제 요약

복면산: 어떤 계산식의 각 숫자들을 특정 문자로 바꾸면 각 문자가 어떤 숫자인지 맞추는 퍼즐.

복면산 문제가 주어질 때 답이 존재하는지 여부를 출력

핵심 아이디어

입력에서 주어진 모든 알파벳에 0부터 9까지의 숫자를 경우의 수대로 다 넣어보고 되는지 확인하면 되는 브루트포스 문제이다.

같은 문자는 같은 숫자에 대응돼야 하고, 서로 다른 문자는 서로 다른 숫자를 나타내기에 알파벳을 딕셔너리로 관리하면 된다. 문자 하나가 숫자 한 자리를 의미하기에 입력으로 들어온 알파벳의 종류가 0~9의 10개를 초과하면 불가능하기에 바로 NO를 출력하면 된다.

check 함수와 convert_word_to_num 함수를 만들었는데, check 함수는 복면산이 성립하는지 체크하는 함수이고, convert_word_to_num은 그 과정에서 필요한, 문자를 숫자로 변환하는 함수이다. check 함수에서는 첫 번째 + 두 번째 = 세 번째 여부를 확인한다.

itertools의 permutations을 쓰는 풀이와 백트래킹을 쓰는 풀이 두 가지로 풀었는데, 둘 다 테스트케이스는 잘 통과하는데 시간 초과가 나온다.

풀이

itertools permutations 사용

# gold4-15811. 복면산?!

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

words = list(map(str, input().split())) # 첫 번째 + 두 번째 = 세 번째

# 그냥 존재하는 알파벳 세트에 0부터 9까지 다 넣어보고 되는지 확인
# 같은 문자는 같은 숫자에 대응되어야 하며, 서로 다른 문자는 서로 다른 숫자를 나타냄 -> 알파벳 종류 11개 넘어가면 불가능 (0~9는 10개)

alphabet_list = sorted(list(set(words[0] + words[1] + words[2])))
alphabet_dict = {}
zero_to_nine = [x for x in range(10)]

def convert_word_to_num(word):
    converted_word = 0
    for x in word:
        # 대응하는 숫자로 변환된 문자
        converted_word = converted_word * 10 + alphabet_dict[x]
    return converted_word

def check():
    word_number_list = [0]*3 # word를 숫자로 변환한 것의 리스트
    for i in range(3):
        word_number_list[i] = convert_word_to_num(words[i])
    if word_number_list[0] + word_number_list[1] == word_number_list[2]:        
        return True
    return False   

if len(alphabet_list) > 10: 
    print("NO")
    exit()

for array in permutations(zero_to_nine, len(alphabet_list)):
    for i in range(len(alphabet_list)):
        alphabet_dict[alphabet_list[i]] = array[i] # alphabet_list의 알파벳과 permutations으로 만들어진 array 값 차례대로 대응

    if check():
        print("YES")
        exit()

print("NO")

백트래킹 사용

# gold4-15811. 복면산?!

import sys
input = sys.stdin.readline

words = list(map(str, input().split())) # 첫 번째 + 두 번째 = 세 번째

# 그냥 존재하는 알파벳 세트에 0부터 9까지 다 넣어보고 되는지 확인
# 같은 문자는 같은 숫자에 대응되어야 하며, 서로 다른 문자는 서로 다른 숫자를 나타냄 -> 알파벳 종류 11개 넘어가면 불가능 (0~9는 10개)

alphabet_list = sorted(list(set(words[0] + words[1] + words[2]))) # words에 있는 알파벳 종류 리스트
alphabet_dict = {}
dict_value_list = []
has_seen_yes = False

# words를 실제 숫자로 바꿈
def convert_word_to_num(word):
    converted_word = 0
    for x in word:
        # 대응하는 숫자로 변환된 문자
        converted_word = converted_word * 10 + alphabet_dict[x]
    return converted_word

# 성립 여부 체크
def check():
    word_number_list = [0]*3 # word를 숫자로 변환한 것의 리스트
    for i in range(3):
        word_number_list[i] = convert_word_to_num(words[i])
    if word_number_list[0] + word_number_list[1] == word_number_list[2]:        
        return True
    return False        

def back():
    global has_seen_yes
    if len(dict_value_list) == len(alphabet_list):
        # 딕셔너리 만들기
        for i in range(len(alphabet_list)):
            alphabet_dict[alphabet_list[i]] = dict_value_list[i] # alphabet_list의 알파벳과 dict_value_list의 숫자 차례대로 대응
        if check():
            print("YES")
            has_seen_yes = True
            exit()            
    for num in range(10):
        if num not in dict_value_list:
            dict_value_list.append(num)
            back()
            dict_value_list.pop()

# 알파벳 종류가 10개 넘어가면 불가능하니까 끝냄
if len(alphabet_list) > 10: 
    print("NO")
    exit()

back()

if not has_seen_yes: print("NO")