[프로그래머스] 파이썬 - 수식 분석하기 (PCCP)

문제

 

풀이

 

구현 문제이다. 

진법변환에 대해 잘 이해하고, 문제를 잘 읽어야 풀 수 있는 문제이다.

문제 자체의 정답은 미지식(x)이 포함된 식에 결과값을 붙여 출력해주면 된다.

 

 

아래는 나의 풀이방법이다.

 

 

1. 입력을 받아 x가 포함되지 않은 정상적인 식(certain_expressions), x가 포함된 식(uncertain_expressions)으로 나눈다.

for expression in expressions:
    x,sign,y,equal_sign,result = expression.split()
    
    if result == 'X':
        uncertain_expressions.append([x,sign,y])
    else:
        certain_expressions.append([x,sign,y,result])

 

2. 각 식의 좌항의 수들 중 가장 큰 수(6)를 찾는다.

 

주어진 입력을 보면

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

 

더해지는 수들(14, 3, 13, 6, 51, 5)에서 가장 큰 수는 6이다. 

n진법을 사용할때, n 이상의 수가 등장할 수 없으므로 위의 입력에서 가능한 진법은 7~9진법이다.

 

3. x가 포함되지 않은 정상적인 식들에 대해 7~9 진법 중 정답이 정상적으로 나오는 진법을 찾는다.

for certain in certain_expressions:
    x,sign,y,result = certain
    # 수식이 정상적으로 동작하는 base들 저장
    can_be_base = []

    for i in range(maxNum + 1,10):
        tmp = get_base_result(x,y,sign,i)     

        if convertToNum(tmp,i) == int(result):              
            can_be_base.append(i)
    bases.append(can_be_base)

 

4. 각 식을 만족하는 진법들의 교집합을 찾는다. 

# 교집합 구하는 함수
def intersection(arrays,maxNum):
    if arrays:
        # 첫 번째 배열을 기준
        intersection = set(arrays[0])

        # 나머지 배열들과 교집합을 계속 구함
        for array in arrays[1:]:
            # 교집합 구하는법
            intersection &= set(array)

        return list(intersection)
    return [i for i in range(maxNum+1,10)]

bases = intersection(bases,maxNum)

 

여기서 예외처리가 필요하다.

이 문제에 반례가 있는데, 입력된 모든 식들에 x가 포함되어있는 경우이다.

이럴 경우 3번이 실행되지 않아 교집합에 입력되는 배열이 빈 배열이 나온다.

따라서 array out of range 오류가 뜨게되므로 예외처리가 필요하다.

 

배열이 비어있는 경우에는 maxNum보다 큰 진법만 bases에 넣어주면 된다.

 

5. x가 포함된 식들에 bases에 있는 진법을 하나씩 대입해본다.

for uncertain in uncertain_expressions:
        x,sign,y = uncertain
        
        # 안겹치도록 음수 설정
        result = -1

        for base in bases:
            tmp = get_base_result(x,y,sign,base) 

            n = int(convertToNum(tmp,base))

            if result < 0:
                result = n
            elif result != n:             
                result = "?"
                break
        
        answer.append(f"{str(x)} {sign} {str(y)} = {result}")

 

만약 도출되는 x의 값이 다를 경우 x = ?로, 같을 경우 해당 숫자를 x에 대입한 후 프린트해준다.

 

 

코드

# 10진수를 base진수로 변환
def convertTobase(number, base):
    # A, B는 음이 아닌 두 자릿수 이하의 정수
    if len(number) == 1:
        return int(number)
    else:
        return base * int(number[0]) + int(number[1])

# base진수를 10진수로 변환
def convertToNum(number, base):
    if number == 0:
        return 0
    string = ''
    while number>0:
        string = str(number % base)+ string
        number //= base
    return int(string)
    
# 교집합 구하는 함수
def intersection(arrays,maxNum):
    if arrays:
        # 첫 번째 배열을 기준
        intersection = set(arrays[0])

        # 나머지 배열들과 교집합을 계속 구함
        for array in arrays[1:]:
            # 교집합 구하는법
            intersection &= set(array)

        return list(intersection)
    return [i for i in range(maxNum+1,10)]

# 어떤 식의 base진법 계산 결과 얻는 함수
def get_base_result(x,y,sign,base):         
    left = convertTobase(x,base)
    right = convertTobase(y,base)

    if sign == '+':
        return left + right
    else:
        return left - right

def solution(expressions):
    answer = [] 
    certain_expressions = []
    uncertain_expressions = []
    bases = []
    maxNum = 0
    
    for expression in expressions:
        x,sign,y,equal_sign,result = expression.split()
        
        # 최소 진법 찾기 
        for i in x:
            maxNum = max(maxNum,int(i))
        for i in y:
            maxNum = max(maxNum,int(i))
            
        if result == 'X':
            uncertain_expressions.append([x,sign,y])
        else:
            certain_expressions.append([x,sign,y,result])

    for certain in certain_expressions:
        x,sign,y,result = certain
        # 수식이 정상적으로 동작하는 base들 저장
        can_be_base = []
        
        for i in range(maxNum + 1,10):
            tmp = get_base_result(x,y,sign,i)     

            if convertToNum(tmp,i) == int(result):              
                can_be_base.append(i)
        bases.append(can_be_base)

    bases = intersection(bases,maxNum)

    for uncertain in uncertain_expressions:
        x,sign,y = uncertain
        
        # 안겹치도록 음수 설정
        result = -1

        for base in bases:
            tmp = get_base_result(x,y,sign,base) 
            n = int(convertToNum(tmp,base))

            if result < 0:
                result = n
            elif result != n:             
                result = "?"
                break   
        answer.append(f"{str(x)} {sign} {str(y)} = {result}")
    return answer

 

프로그래머스