[프로그래머스/LV3] 수식 복원하기

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

프로그래머스

 

Status : Solved

 

Time : 00:50:24

 

---

 

문제 설명

 

문제 설명은 링크를 참조해 주세요!

 

입력 및 출력

 

예시는 링크를 참조해 주세요!

 

---

 

풀이

 

하나씩 구현하면서 최소 기능 단위의 구현을 익혀보자! 하고 생각했다가 근 1시간을 쏟아부은 문제. 클린한 코드의 길은 어렵기만 하다(이렇게 나눠서 구현했음에도 더러운 건 비밀 ㅎ)

 

그럼 각 컴포넌트별로 살펴보도록 하자.

 

from typing import List

def calculate(expr: str, left: str, right: str) -> int:
    return int(left) + int(right) if expr == '+' else int(left) - int(right)

def convert_base(string_num: str, init_base: int, dest_base: int) -> str:
    try:
        num = int(string_num, init_base)
        result = ''
        while num:
            result += str(num % dest_base)
            num //= dest_base
        return result[::-1] if result else '0'
    except:
        return 'invalid'

def is_target_expression(expression: str) -> bool:
    return expression[-1] == 'X'

• calculate : 기본 함수, 파이썬에는 문자열을 그대로 계산해주는 expr 함수가 있긴 하다.

https://docs.python.org/ko/3.13/library/functions.html#exec

Built-in Functions

그냥 빌트인 함수를 사용해도 된다.

 

• convert_base : 문제의 핵심. n진법을 m진법으로 변환하는 함수이다.
  • 우리는 이 함수를 통해 여러 가지를 체크해야 한다.
  • 가령, 시작 진법인 n진법 기준으로 올바른 진법인지 체크해야 한다. 가령 333은 절대 2진법일 수 없다.
    • 이는 try - except와 int를 사용해서 해결했다. int는 base 인자를 넣어주면 그 진법이라고 인식하고 10진법으로 변환해준다. 만약 실패하면 except문에 의해 invalid로 반환될 것이다.
  • 또한, 이를 또 m진법으로 바꿔줘야한다.
    • 파이썬 내장 함수에는 10진법을 m진법으로 바꿔주는 코드가 없는 걸로 알아서, 직접 구현했다.
• is_target_expression : 기본 함수. expression 하나가 우리가 구해야 할 expression인지 판단한다.

---

이제 이 함수들을 기본으로 확장된 함수를 작성할 차례다. 먼저 base 후보를 구해보자.

 

def is_matched_base(base: int, expression: str) -> bool:
    left, expr, right, _, result = expression.split()
    left = convert_base(left, base, 10)
    right = convert_base(right, base, 10)
    result = convert_base(result, base, 10)
    
    if left == 'invalid' or right == 'invalid':
        return False
    if is_target_expression(expression) :
        return True
    if result == 'invalid':
        return False
        
    return calculate(expr, left, right) == int(result)

def find_bases(expressions: List[str]) -> List[int]:
    bases = []
    for base in range(2, 10):
        is_matched = True
        for expression in expressions:
            if not is_matched_base(base, expression):
                is_matched = False
                break
        if is_matched:
            bases.append(base)
    return bases

 

• is_matched_base : 입력된 base가 어떤 expression 내에서 유효한 base(진수)인지 판단한다. 다음을 기준으로 판단해보자.
  • left, right 숫자가 정상적인 base인지
    • 만약 target expression이 아니라면, 연산 결과값인 result 역시 유효한 base 인지
    • 그렇게 반환한 left, right, result 연산 결과가 동일한지
• find_bases : expressions가 입력으로 주어졌을 때 base 후보를 구하는 함수이다. 문제 정의상 base는 2~9진수이므로 이를 순회하도록 한다. 또한, 모든 expression에서 base후보가 is_matched_base를 만족한다면, 이 base는 후보가 될 수 있다.

---

이렇게 base후보를 구했으니, 이제 target인 표현식들에 대입해보자.

 

def correct_target_expression(bases: List[int], expression: str) -> str:
    left, expr, right, equal, _ = expression.split()
    answer_set = set()
    for base in bases:
        l = convert_base(left, base, 10) 
        r = convert_base(right, base, 10) 
        if l == 'invalid' or r == 'invalid' :
            continue
    
        res = calculate(expr, l, r)
        print(res, base)
        res = convert_base(str(res), 10, base)
        print(res)
        answer_set.add(res)
    print(answer_set)
    res = list(answer_set)[0] if len(answer_set) == 1 else '?'
    return ' '.join((left, expr, right, equal, res))

def correct_expressions(bases: List[int], expressions: List[str]) -> List[str]:
    result = []
    for expression in expressions :
        if not is_target_expression(expression):
            continue
        res = correct_target_expression(bases, expression)
        result.append(res)
    return result

 

• correct_target_expression : 어떤 target expression과 base 후보를 인자로 받는다. base 후보에 따라 target expression의 우변에 base진법의 결과값이 생성될 것이다. 이 결과값을 추출하도록 한다. 만약 결과값이 2 이상이라면 하나로 확정할 수 없으므로 '?'로, 그렇지 않으면 그 결과값을 대입해서 반환하도록 하자.
• coreect_expressions : 모든 expression을 순회하며, target expression일 경우 앞서 정의한 correct_target_expression으로 수식을 변환한다. 그 결과값이 곧 문제에서 요구하는 정답이다.

 

풀이 코드

from typing import List

def calculate(expr: str, left: str, right: str) -> int:
    return int(left) + int(right) if expr == '+' else int(left) - int(right)

def convert_base(string_num: str, init_base: int, dest_base: int) -> str:
    try:
        num = int(string_num, init_base)
        result = ''
        while num:
            result += str(num % dest_base)
            num //= dest_base
        return result[::-1] if result else '0'
    except:
        return 'invalid'

def is_target_expression(expression: str) -> bool:
    return expression[-1] == 'X'

def is_matched_base(base: int, expression: str) -> bool:
    left, expr, right, _, result = expression.split()
    left = convert_base(left, base, 10)
    right = convert_base(right, base, 10)
    result = convert_base(result, base, 10)
    
    if left == 'invalid' or right == 'invalid':
        return False
    if is_target_expression(expression) :
        return True
    if result == 'invalid':
        return False
        
    return calculate(expr, left, right) == int(result)

def find_bases(expressions: List[str]) -> List[int]:
    bases = []
    for base in range(2, 10):
        is_matched = True
        for expression in expressions:
            if not is_matched_base(base, expression):
                is_matched = False
                break
        if is_matched:
            bases.append(base)
    return bases

    
def correct_target_expression(bases: List[int], expression: str) -> str:
    left, expr, right, equal, _ = expression.split()
    answer_set = set()
    for base in bases:
        l = convert_base(left, base, 10) 
        r = convert_base(right, base, 10) 
        if l == 'invalid' or r == 'invalid' :
            continue
    
        res = calculate(expr, l, r)
        print(res, base)
        res = convert_base(str(res), 10, base)
        print(res)
        answer_set.add(res)
    print(answer_set)
    res = list(answer_set)[0] if len(answer_set) == 1 else '?'
    return ' '.join((left, expr, right, equal, res))

def correct_expressions(bases: List[int], expressions: List[str]) -> List[str]:
    result = []
    for expression in expressions :
        if not is_target_expression(expression):
            continue
        res = correct_target_expression(bases, expression)
        result.append(res)
    return result
        

def solution(expressions):
    bases = find_bases(expressions)
    answer = correct_expressions(bases, expressions)
    
    return answer