[프로그래머스] 수식 복원하기 (Lv 3)

https://school.programmers.co.kr/learn/courses/30/lessons/340210

프로그래머스

 

기본적으로 10진 -> N,  N-> 10을 생각해야 합니다. 각 수식별로, 가능/불가능 여부를 모두 따져야 합니다.
(아마 하나에서 10진으로 안될 경우 맞는 값을 찾을 경우 나머지를 볼 필요는 없을거라 이것의 최적화도 될거긴 합니다.)

그리고,추가로 N진법의 숫자 범위를 고려해야 합니다. 숫자 범위에 맞지 않는 진법을 걸러낸 다음에,
나머지 중에서 연산의 결과를 체크하는 방식으로 가능한 N진법을 다룬 다음 X가 들어간 식의 N진 계산을 진행, 정답의 경우의 수가 2개 이상이면 ?,  1개면 그것을 넣습니다. 기본적으로 N진법의 계산은 N진 -> 10진 변환후 계산 -> 결과값의 N진 변환으로 진행합니다.

전형적인 빡구현 피지컬 문제입니다.  PCCP 시험장이었으면 타임어택에 쫓겨 고생 좀 했을 거 같습니다.
실제로도 40~50분 박았습니다... 순수하게 피지컬로 오래 걸린 문제입니다.

def get_adic_num(num, adic):
    hunds = num // 100
    tens = (num % 100) // 10
    ones = num % 10
    
    return hunds * (adic ** 2) + tens * adic + ones


def adic_change(num, adic):
    residue_list = []
    if num == 0:
        return "0"
    while num > 0:
        cur_r = num % adic
        residue_list.append(str(cur_r))
        num = num // adic
    answer = ''
    for i in range(len(residue_list)):
        answer += residue_list[-1-i]
    return answer


def solution(expressions):
    answer = []
    x_list = []
    padic_dict = {2:1, 3:1, 4:1, 5:1,
                  6:1, 7:1, 8:1, 9:1}
    check_num = ['8', '7', '6', '5', '4', '3', '2', '1']
    # step 1. 사용된 가장 큰 값을 찾는다. 이것이 진법의 후보가 된다.
    max_num = -1
    for cur_exp in expressions:
        if "X" in cur_exp:
            x_list.append(cur_exp)
        for cur_c in check_num:
            if cur_c in cur_exp:
                if max_num < int(cur_c):
                    max_num = int(cur_c)
    for i in range(2, 10):
        if i <= max_num:
            padic_dict[i] = 0
    # step 2. 계산식을 돌면서, 진법 판단을 해야 한다.
    # 10진법으로도 맞을 경우 계산할 이유가 없지만
    # 10진법으로 되지 않을 경우 다른 진법이라는 이유이므로
    # 진법 판정에 들어간다. -> 이 경우 이론상 해는 유일해일 것이다.
    # 그리고 만일 식에 x가 있다면 x_list에 넣어 정답을 출력할 준비를 하자.
    for cur_exp in expressions:
        if "X" not in cur_exp:
            # 수식은 수 기호 수 등호 수 구조이다.
            math_list = cur_exp.split(" ")
            # 앞으로 계속 수식 계산 해야하니까, 지금 바꿔둔다.
            math_list[0] = int(math_list[0])
            math_list[2] = int(math_list[2])
            math_list[4] = int(math_list[4])
            flag = True
            tenadic_answer = 0
            
            if math_list[1]=="+":
                if math_list[0] + math_list[2] != math_list[4]:
                    tenadic_answer = math_list[0] + math_list[2]
                    flag = False

            elif math_list[1] == "-":
                if math_list[0] - math_list[2] != math_list[4]:
                    tenadic_answer = math_list[0] - math_list[2]
                    flag = False
                    
            # 진법이 안 맞다는 거니까.
            if not flag:
                for cur_adic in range(9, 1, -1):
                    if padic_dict[cur_adic] == 0:
                        pass
                    else:
                        num_1st = get_adic_num(math_list[0], cur_adic)
                        num_2nd = get_adic_num(math_list[2], cur_adic)
                        num_ans = get_adic_num(math_list[4], cur_adic)
                        if math_list[1]=="+":
                            if num_1st + num_2nd != num_ans:
                                padic_dict[cur_adic] = 0
                        elif math_list[1] == "-":
                            if num_1st - num_2nd != num_ans:
                                padic_dict[cur_adic] = 0
    ok_adic = []
    for p in padic_dict:
        if padic_dict[p] == 1:
            ok_adic.append(p)
    
    final_answer = []
    # 이 시점에서 ok_adic은 후보가 된다. 이제 X가 있는 값을 계산하자. 역으로.
    for cur_x in x_list:
        # 정답 후보를 넣을 것이다.
        answer_cand = []
        math_list = cur_x.split(" ")
        math_list[0] = int(math_list[0])
        math_list[2] = int(math_list[2])
        for cur_adic in ok_adic:
            num_1st = get_adic_num(math_list[0], cur_adic)
            num_2nd = get_adic_num(math_list[2], cur_adic)
            if math_list[1] == "+":
                result_num = adic_change(num_1st + num_2nd, cur_adic)
            elif math_list[1] == "-":
                result_num = adic_change(num_1st - num_2nd, cur_adic)
            answer_cand.append(result_num) # 문자열로 들어오는 상태임.
        answer_cand = list(set(answer_cand))
        if len(answer_cand) == 1:
            math_list[4] = answer_cand[0]
        else:
            math_list[4] = "?"
        math_list = [str(x) for x in math_list]
        final_answer.append(" ".join(math_list))
    return final_answer