코딩 테스트(Python) [PCCP 기출문제] 4번 / 수식 복원하기

문제 설명

당신은 덧셈 혹은 뺄셈 수식이 여러 개 적힌 고대 문명의 유물을 찾았습니다. 이 수식들을 관찰하던 당신은 이 문명이 사용하던 진법 체계가 10진법이 아니라는 것을 알아냈습니다. (2 ~ 9진법 중 하나입니다.)

수식들 중 몇 개의 수식은 결괏값이 지워져 있으며, 당신은 이 문명이 사용하던 진법에 맞도록 지워진 결괏값을 채워 넣으려 합니다.

다음은 그 예시입니다.

<수식>

14 + 3 = 17 13 - 6 = X 51 - 5 = 44

• X로 표시된 부분이 지워진 결괏값입니다.

51 - 5 = 44에서 이 문명이 사용하던 진법이 8진법임을 알 수 있습니다. 따라서 13 - 6 = X의 지워진 결괏값을 채워 넣으면 13 - 6 = 5가 됩니다.

다음은 또 다른 예시입니다.

<수식>

1 + 1 = 2 1 + 3 = 4 1 + 5 = X 1 + 2 = X

주어진 수식들에서 이 문명에서 사용한 진법이 6 ~ 9진법 중 하나임을 알 수 있습니다.

1 + 5 = X의 결괏값은 6진법일 때 10, 7 ~ 9진법일 때 6이 됩니다. 이와 같이 결괏값이 불확실한 수식은 ?를 사용해 1 + 5 = ?와 같이 결괏값을 채워 넣습니다.

1 + 2 = X의 결괏값은 6 ~ 9진법에서 모두 3으로 같습니다. 따라서 1 + 2 = X의 지워진 결괏값을 채워 넣으면 1 + 2 = 3이 됩니다.

덧셈 혹은 뺄셈 수식들이 담긴 1차원 문자열 배열 expressions가 매개변수로 주어집니다. 이때 결괏값이 지워진 수식들의 결괏값을 채워 넣어 순서대로 문자열 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

 

def solution(expressions):
    # 진법으로 숫자를 변환하는 함수
    def trans(a, t):
        if a == 0:
            return 0  # 숫자가 0이면 그대로 반환
        temp = []
        while a:
            temp.append(str(a % t))  # 현재 자리에서의 나머지를 리스트에 저장
            a //= t  # 다음 자리수를 계산
        return int(''.join(temp[::-1]))  # 결과를 뒤집어서 반환 (큰 자리수부터 표시)

    # 표현식 계산 함수 (진법 변환 포함)
    def calculate(expression, t):
        exp = expression.split()  # 표현식을 공백으로 분리
        a1, a2 = int(exp[0], t), int(exp[2], t)  # 두 피연산자를 진법으로 변환
        result = 0
        if exp[1] == '+':  # 덧셈 연산
            result = a1 + a2
        else:  # 뺄셈 연산
            result = a1 - a2
        return trans(result, t)  # 계산 결과를 다시 진법으로 변환하여 반환

    # 표현식의 결과가 주어진 진법에서 성립하는지 확인하는 함수
    def check_calculate(expression, t):
        exp = expression.split()
        if exp[4] != 'X':  # 결과값이 'X'가 아닌 경우만 확인
            a1, a2, result = int(exp[0], t), int(exp[2], t), int(exp[4], t)
            if exp[1] == '+':  # 덧셈 연산
                return a1 + a2 == result
            else:  # 뺄셈 연산
                return a1 - a2 == result

    # 표현식에 대해 가능한 진법을 찾는 함수
    def find_base(expression):
        bases = []  # 가능한 진법의 후보 저장
        exp = expression.split()
        # 'X'를 제외한 숫자 부분에서 최소 필요한 진법 계산
        exp2 = ''.join(expression).replace(' ', '').replace('X', '')
        for i in exp2:
            if i.isdigit():
                bases.append(int(i) + 1)  # 숫자의 최댓값 + 1이 최소 진법
        base_candidate = max(bases)  # 최소 진법 후보 계산
        base = []
        for i in range(2, 10):  # 진법 범위는 2~9
            if i >= base_candidate:
                base.append(i)
        result = base

        # 결과값이 'X'가 아닌 경우, 진법의 유효성 확인
        if exp[4] != 'X':
            temp = []
            for base in result:
                if not check_calculate(expression, base):  # 조건을 만족하지 않는 진법 필터링
                    temp.append(base)
            for t in temp:
                result.remove(t)

        return result  # 가능한 진법 리스트 반환

    # 결과값이 'X'인 표현식 저장
    unknown = []
    # 초기 진법 후보 (2~9)
    bases = [i for i in range(2, 10)]

    # 각 표현식을 순회하며 가능한 진법을 좁혀 나감
    for expression in expressions:
        exp = expression.split()
        if exp[4] == 'X':  # 결과값이 'X'인 경우 따로 저장
            unknown.append(expression)
        # 표현식에서 가능한 진법 계산
        a = find_base(expression)
        # 현재 후보 진법과 교집합을 계산
        temp = []
        for k in a:
            if k in bases:
                temp.append(k)
        bases = temp  # 후보 진법 업데이트

    # 최종 답안을 저장할 리스트
    answer = []
    for expression in unknown:
        temp = set()  # 각 진법에서 계산된 결과값 저장
        for t in bases:
            temp.add(calculate(expression, t))  # 가능한 진법에서 결과값 계산
        # 결과값이 유일하면 그대로 저장, 여러 개라면 '?'로 표시
        if len(temp) == 1:
            answer.append(expression[:-1] + str(temp.pop()))
        else:
            answer.append(expression[:-1] + '?')

    return answer