[Python | 프로그래머스 | Lv_3] 수식 복원하기 (PCCP 기출문제)

😉 아이디어

1. _!expressions!_ digit 중 가장 큰 숫자를 선별하고 +1 해주어 2~9 진수 중 반복 단위를 최소화

2. 예상 진수를 순회하며 _!10진수!_로 변환하고 값이 일치하는지 확인(X가 없는 계산식에만 적용)

3. 주어진 식을 모두 일치시키면 _!candidates!_ 변수에 후보군으로 저장

4. _!candidates!_ 변수를 순회하며 X가 있는 값들을 계산, 단 이전 후보군과의 계산 결과가 다르면 _!?!_로 표기

😉 풀이

def solution(expressions):
    answer = []
    non_x_exprs = []
    x_exprs = []
    exprs = []
    for expression in expressions:
        exprs.append(expression.split(" "))
        if 'X' in expression:
            x_exprs.append(expression.split(" "))
        else:
            non_x_exprs.append(expression.split(" "))
        
    min_base = get_minimum_base(exprs)
    candidates = get_base_candidates(non_x_exprs, min_base)
    guessed_values = guess_values(x_exprs, candidates)
    
    for i in range(len(x_exprs)):
        x_exprs[i][-1] = str(guessed_values[i])
        answer.append(" ".join(x_exprs[i]))
        
    return answer

def guess_values(exprs, candidates):
    converted_values = [-1] * len(exprs)
    
    for candidate in candidates:
        for i, expression in enumerate(exprs):
            left_num, operator, right_num, _, result = expression
            
            decimal_left_num = int(str(left_num), candidate)
            decimal_right_num = int(str(right_num), candidate)
            
            calc_result = -1
            if operator == '+':
                calc_result = convert_to_base(decimal_left_num + decimal_right_num, candidate)
            else:
                calc_result = convert_to_base(decimal_left_num - decimal_right_num, candidate)
                
            if converted_values[i] == -1:
                converted_values[i] = calc_result
            else:
                if converted_values[i] != calc_result:
                    converted_values[i] = '?'
                    
    return converted_values

def get_base_candidates(exprs, min_base):
    candidates = []
    for i in range(min_base, 10):
        is_valid_base = True
        for expression in exprs:
            left_num, operator, right_num, _, result = expression
            
            decimal_left_num = int(left_num, i)
            decimal_right_num = int(right_num, i)
            decimal_result_num = int(result, i)
            
            # print(f'left = {decimal_left_num}, right = {decimal_right_num}, result = {decimal_result_num}')
            
            if operator == '+':
                if decimal_left_num + decimal_right_num != decimal_result_num:
                    is_valid_base = False
            else:
                if decimal_left_num - decimal_right_num != decimal_result_num:
                    is_valid_base = False
        
        if is_valid_base:
            candidates.append(i)
                
    return candidates

def get_minimum_base(exprs):
    max_digit = 0
    
    for expression in exprs:
        left_num, operator, right_num, _, result = expression

        for idx in range(len(left_num)):
            max_digit = max(max_digit, int(left_num[idx]))

        for idx in range(len(right_num)):
            max_digit = max(max_digit, int(right_num[idx]))

        if result != "X":
            for idx in range(len(result)):
                max_digit = max(max_digit, int(result[idx]))
    
    return max_digit + 1

def convert_to_base(decimal_number, base):
    if decimal_number == 0:
        return 0
    
    reversed_base_digits = ''
    while decimal_number > 0:
        decimal_number, remainder = divmod(decimal_number, base)
        reversed_base_digits += str(remainder)
    
    return reversed_base_digits[::-1]

✔️ 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/340210