[BOJ][Python3/PyPy3] 15811 - 복면산?!

solved.ac 기준 실버2 수준이었던 제게는 매우 어려웠던 스터디 연습 문제

이 문제를 푸는 과정을 적으며, 효율적인 알고리즘에 대한 복기를 해보려고 합니다.

 

[문제]

복면산이란 수학 퍼즐의 일종으로,

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

 

=> 각 문자가 어떤 '숫자' 인지 맞추는 퍼즐입니다.

저는 '숫자'와 '수'를 혼동해서 "A = 10 같은 것도 가능할까?" 같은 쓸데없는 고민도 했었습니다.

 

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

단, 같은 문자는 같은 숫자에 대응되어야 하며,

서로 다른 문자는 서로 다른 숫자를 나타낸다. 또한, 수는 0으로 시작할 수 있다.

 

=>아래 예시 힌트가 없었다면 빼먹고 체크를 안할 수도 있었던 조건 같습니다.

문제를 끝까지 꼼꼼하게 읽으며 조건을 확인하는 습관을 가져야겠다고 생각했습니다.

 

[입력]

세 단어가 공백을 두고 주어진다. 첫 번째 단어와 두 번째 단어를 더한 결과가 세 번째 단어임을 의미한다.

단어는 공백 없이 알파벳 대문자로만 이루어져 있으며 각 단어의 길이는 18자리를 넘지 않는다.

 

=> 백준에서 주어지는 이 조건을 항상 확인하고,

디버깅시 경계값을 넣어보면서 확인하는 습관을 가져야겠다는 생각을 다시 했습니다.

 

[출력]

해답이 존재한다면 YES를, 그렇지 않다면 NO를 한 줄에 출력

 

------------------------------------------------------------------------

 

사실 아무것도 안알려주고 그냥 풀어보라고 던져줬다면 시도조차 못했을 것 같습니다.

동아리 스터디에서 "순열/조합을 활용한 브루트포스" 라는 주제의 연습문제로 주어졌기에

순열의 활용, 완전탐색 이라는 두가지 핵심 아이디어를 가진 채 시작할 수 있었습니다.

 

저는 딕셔너리를 활용한 아이디어를 떠올렸습니다.

알파벳에 숫자가 하나씩 대응하는 관계가

딕셔너리의 key와 value사이 관계와 비슷하다고 생각했습니다.

 

예를 들어

SEND 라는 단어가 있다면

'S' 'E' 'N' 'D'

========

0   1   2   3

0   1   2   4

0   1   2   5

0   1   2   6

:

:

 

각 순열 경우의 수 케이스에서 문자와 숫자를 매칭하고

매칭한 그 케이스가 가능한 케이스인지 계산시켜본다음

식이 성립한다면 YES를 아니라면 NO를 출력하도록 합니다.

 

1. 메모리 초과

파이썬의 itertools 를 이용해 순열 반복자를 만든다음 그걸 리스트에 넣었습니다.

그리고 그 리스트 채로 for문을 돌리니 메모리 초과가 나왔습니다.

 

예시 문제 중 SEND MORE MONEY 케이스는 188만가지가 넘는 순열 케이스를 보유하는데

(10개의 숫자 중 8가지 종류의 문자가 있으므로)

188만가지의 순열 조합을 모두 리스트에 넣으니 당연한 결과인 것 같습니다.

 

순열 반복자를 리스트에 넣지 않고 반복자 째로 사용하여 메모리 초과 문제를 해결하였습니다.

전에 배웠던 반복자의 개념을 실제 문제에 적용해볼 수 있는 기회였습니다.

 

2. 예외 케이스

문자열의 길이는 최대 18입니다. 그리고 알파벳의 종류는 26가지입니다.

10개 이상의 알파벳 종류가 충분히 등장할 수 있는 환경인데,

문제에서 서로 다른 알파벳은 서로 다른 숫자를 가리킨다고 하였으니

10개 이상의 알파벳이 등장하면 문제의 답은 계산할 필요도 없이 존재하지 않습니다.

 

이 예외케이스를 먼저 분리하여놓고 알고리즘을 실행시켜야했습니다.

 

3. 시간 초과

저에게는 복면산 파이썬 문제의 꽃, 핵심 그 자체였습니다.

제 스스로는 이 문제를 결국 해결하지 못하여 스터디 멘토님들의 도움을 받아야만 했습니다.

 

시간초과의 원인은 여러가지가 있었습니다.

 

1. 문자열 계산 / 처리

=> 문자열 계산은 숫자계산으로 바꾸고, 문자열을 리스트로 처리하여 시간을 줄였습니다.

 

2. 숫자 계산

숫자로 계산할 때,

저는 딕셔너리 속 문자에 연결된 숫자에 그 숫자의 자리수 만큼 10을 매번 곱해주어 숫자로 변환하였는데요

이 부분때문에 시간초과 문제를 해결할 수 없었습니다.

 

저는 '4' '3' '2' '1' 을 계산하기 위해

4 * 10 * 10 * 10

3 * 10 * 10

2 * 10

1

 

4번 + 3번 + 2 번 + 1번 = 10번의 계산을 했습니다.

18자리의 수였다면..

19*18/2 = 171 번의 계산인데

 

18자리의 문자가 최대 3번 등장 가능하니..

171 * 3 = 513번의 계산을 해야하는 최악의 경우가 있었습니다.

 

선배님께서 주신 아이디어는 다음과 같습니다.

1

2 * (10) => 10은 변수에 미리 저장

3 * ((10) * 10) => 10이 저장된 변수에 10만 한번 더 곱해줌

4 * (((10) * 10) * 10)

 

이렇게 하면

0번 + 1번 + 2번 + 2번 이므로 5번만에 끝납니다.

18자리의 수였다면

0번 1번 2번 2번 2번 ... == 33번의 계산만에 끝나죠.

앞에서 했던 계산을 또 하지 않으니 효율성의 차이가 심하게 납니다.

이렇게 제출하니 통과가 되었네요..

 

그래서 다음과 같은 코드를 완성했습니다.

import sys
import itertools
from timeit import timeit
def judge():
    fir = sec = trd = 0
    for ch in words[0]:
        fir *= 10
        fir += alpb[ch]

    for ch in words[1]:
        sec *= 10
        sec += alpb[ch]

    for ch in words[2]:
        trd *= 10
        trd += alpb[ch]

    return fir + sec == trd
    #return word_num[0] + word_num[1] == word_num[2]

words = list(map(list,sys.stdin.readline().split())) #단어 리스트
nums = [0,1,2,3,4,5,6,7,8,9]
alpb = dict()

for i in range(3):
    for ch in words[i]:
        if ch not in alpb:
            alpb[ch] = -1

alpb_num = len(alpb)
lens = [len(words[0]),len(words[1]),len(words[2])]
word_num = [0, 0, 0]

if alpb_num > 10:
    print('NO')

else:
    for p in (itertools.permutations(nums, alpb_num)):
        k = 0; find = False
        for i in alpb.keys():
            alpb[i] = p[k] #순열과 알파벳 딕셔너리 매칭
            k += 1
        # print(alpb)
        if judge():
            print('YES')
            find = True
            break

    if not find:
        print('NO')

스스로 공부해야할 부분이 아직 많았다는 것을 되새기게 해준 문제라고 생각합니다.

더 열심히 노력해야겠네요..