수식 복원하기

문제 설명

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

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

다음은 그 예시입니다.

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

 

해당 문제는 몇가지 주요 단계로 나누어서 해결했습니다.

진수 변환: 산술 연산을 수행하려면 진수 간에 숫자를 변환해야 합니다.
평가: 각 표현식에 대해 결과를 직접 계산할 수 있는지 또는 알 수 없는 사항을 알아내야 하는지 결정합니다.
결과 형식화: 마지막으로 지정된 출력 요구 사항에 따라 결과 형식을 지정합니다.

 

import re
def int_to_base(num, base):
    if num == 0:
        return "0"
    digits = []
    while num:
        digits.append(int(num % base))
        num //= base
    return ''.join(str(x) for x in digits[::-1])

def solution(expressions):
    answer = []
    
    max_num = max([int(i) for i in ''.join(expressions) if i.isdigit()])
    possible = [i for i in range(max_num+1,10)]
    
    expressions.sort(key = lambda x : 0 if x[-1]=='X' else int(x[-2:]), reverse = True)
    
    for e in expressions:
        num1,calc,num2,equal,result = re.split(r'(\+|\-|\=)', e)
        
        if result.strip() != 'X':
            for i in possible[:]:
                base_num1,base_num2,base_result =int(num1,i),int(num2,i),int(result,i)
                
                if calc == '+':
                    calc_result = base_num1 + base_num2
                    
                else:
                    calc_result = base_num1 - base_num2
                    
                if calc_result != base_result:
                    possible.remove(i)
        else:
            test = set()
            for i in possible:
                base_num1,base_num2 =int(num1,i),int(num2,i)
                
                if calc == '+':
                    test.add(int_to_base(base_num1 + base_num2,i))
                    
                else:
                    test.add(int_to_base(base_num1 - base_num2,i))
                    
            if len(test) == 1:
                result_value = list(test)[0]
                answer.append(f'{e[:-1]}{result_value}')
            else:
                answer.append(f'{e[:-1]}?')
            
    return answer

 

1. 코드의 주요 구성 요소
   기본 변환 함수: int_to_base 함수는 정수를 지정된 기본으로 변환합니다. 숫자를 밑수로 계속해서 나누고 나머지를 기록하여 새 밑수에 숫자를 만듭니다.
   
   
2. 식 정렬: 식은 알 수 없는 'X'가 포함되어 있는지 여부에 따라 정렬됩니다. 이를 통해 우리는 미지수를 처리하기 전에 완전히 정의된 표현식의 우선순위를 지정할 수 있습니다.
   
   
3. 표현식 평가: 각 표현식에 대해 다음을 수행합니다.
   
   
4. 결과가 알려진 경우 가능한 모든 밑수에서 값을 계산하고 산술이 참인지 확인합니다.
   결과를 알 수 없는 경우 가능한 모든 값을 파악하여 몇 개의 고유한 값을 도출할 수 있는지 확인합니다.
   출력: 결과가 형식화되어 답변 목록에 추가됩니다. 고유한 결과를 찾을 수 있으면 직접 추가됩니다. 그렇지 않으면 자리 표시자(?)가 사용됩니다.