백준 15811번 - 복면산!?(Python)

초급 스터디 - 01.5 Permutation and Combination 연습문제 F

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

15811번: 복면산?!

문제

복면산 문제인데, 파이썬의 itertools 라이브러리를 잘 사용하면 쉽게 풀 수 있을 것 같았다.

 

코드 설명

우선 첫 번째 단어와 두 번째 단어, 그리고 정답 단어를 각각 op1, op2, ans로 입력받은 다음, 집합으로 변형시켜 중복을 없애주고 다시 정렬된 리스트로 형식 변환을 시켜주었다. 따라서 alphaList에는 입력받은 알파벳이 중복 없이 정렬되어 있는 상태로 저장되어 있다.

각 알파벳과 대응하는 수열을 얻기 위해 itertools.permutation 메소드를 사용해서 0부터 9까지의 수에서 식에 포함된 알파벳의 개수만큼 수를 뽑아 순열을 만들었다. 또한 딕셔너리를 이용해 key(알파벳)과 value(숫자)의 값을 쉽게 매칭할 수 있도록 했다.

28~36번째 줄의 반복문은 순열을 생성한 다음

1. 알파벳의 개수가 10보다 큰지 확인한다. 10보다 크면 0~9까지의 수로 모든 알파벳을 커버할 수 없기 때문이다.
2. 알파벳의 개수가 10보다 작다면 알파벳의 개수만큼 반복문을 실행하여 각 알파벳과 k에 저장된 순열의 숫자가 인덱스 번호대로 매치하도록 저장했다.
3. solve() 메소드를 실행시킨다. solve()는 op1, op2, ans 각각에 들어있는 알파벳과 대응하는 숫자를 가져와 정수로 변환한 다음, op1 + op2 == ans의 결과를 bool type로 반환하는 함수이다. int(op1)와 같이 변환하는 방법도 있지만, 시간복잡도를 고려했을 때 solve()에서처럼 직접 자릿수를 곱하여 계산하는 게 더 빠르다고 한다.

 

나의 코드

from itertools import permutations
import sys


nums = [x for x in range(10)]
op1, op2, ans = map(list, sys.stdin.readline().split())


def solve():
    fir = sec = thi = 0
    for i in op1:
        fir *= 10
        fir += alnumDict[i]
    for i in op2:
        sec *= 10
        sec += alnumDict[i]
    for i in ans:
        thi *= 10
        thi += alnumDict[i]
    return thi == fir + sec


alphaList = sorted(list(set(op1 + op2 + ans)))

alnumDict = {}
alphaLength = len(alphaList)

for k in permutations(nums, alphaLength):
    if alphaLength > 10:
        break
    for i in range(alphaLength):
        alnumDict[alphaList[i]] = k[i]

    if solve():
        print("YES")
        exit(0)

print("NO")