[Python] [PCCP 기출문제] 4번 / 수식 복원하기

 

 

 

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

프로그래머스

 

문제 3줄 요약

1. 덧셈, 뺄셈 수식이 있다.

2. 수식은 10진법이 아니라 2~9진법을 사용하고 있다.

3. 몇 개의 수식은 결괏값이 지워져 있으며, 진법에 맞도록 지워진 결괏값을 채워 넣어라.

 

---

 

처음엔 입출력 예시를 보고 한참을 생각했다.

수식이 이게 어떻게 맞다는 거지..? ㅋㅋㅋ

 

 

예시 하나만 같이 살펴보자.

 

"14 + 3 = 17" 과 "51 - 5 = 44"를 힌트로 삼아

"13 - 6 = X"의 값을 알아내야 하는 예시이다.

 

 

대뜸 8진법임을 알 수 있다는데,

2~9 진법 중 8진법만 저 수식이 가능한가 보다.

 

51(8) = 8*5 + 1*1 = 41(10)

5 = 1*5 = 5(10)

44 = 8*4 + 1*4 = 36(10)

 

41 - 5 = 36..

맞긴 맞네?

 

근데 2부터 9까지의 모든 진법을 계산하는 건

비효율적이겠죠?

 

 

이 예시에서는

왜 6~9진법 중 하나임을 알 수 있다고 했을까?

 

수식에 포함되어 있는 숫자들이

1 ~ 5까지 존재하니 일단 2~5까지의 진법은 아닌 것으로 판단한 것인데요..!

 

이런 방식으로

탐색해야 할 진법을 최소화하는 게 이 문제의 핵심!!

 

여기까지 코드로 작성해 본다면?

 

def solution(expressions):
    answer, answer_format = [], []
    max_format, hint = 0, []
    for e in expressions:
        num1, func, num2, _, ans = e.split(" ")
        
        for idx in range(len(num1)): max_format = max(max_format, int(num1[idx]))
        for idx in range(len(num2)): max_format = max(max_format, int(num2[idx]))
        
        if ans != "X": 
            hint.append(e)
            for idx in range(len(ans)): max_format = max(max_format, int(ans[idx]))
        else: answer.append(e)

 

좌/우 숫자, 정답에 숫자가 있는 경우

모든 자리의 숫자를 확인해서 탐색해야 할 진법을 최소화해줬습니다.

 

만일 이 문제를 풀었는데,

점수가 82.6 / 100 이 나왔다.

 

좌/우 숫자의 모든 자리 숫자를 확인하지 않은 것.

 

점수가 95.7 / 100 이 나왔다면?

정답의 모든 자리 숫자를 확인하지 않은 것.

 

왜 이렇게 상세하게 알고 있냐면,

제가 그렇게 풀어서 틀렸었습니다. 하하..

 

여튼

수식의 답이 X가 아닌 숫자로 주어진 경우에는

힌트라는 리스트에 추가해 줬는데요.

 

힌트에 들어간 수식은

진법을 돌며 어떤 진법이 이에 해당하는지 계산을 해줄 것이고,

X로 채워진 수식의 정답을 구해볼 것입니다!

 

def NToTen(n, num):
    if len(num)==1: return int(num)

    number = 0
    for idx in range(len(num)):
        number += int(num[idx])*(n**(len(num)-1-idx))

    return number

for n in range(max_format+1, 10):
    check = 1
    for h in hint:
        num1, func, num2, _, ans = h.split(" ")
        num1, num2, ans = NToTen(n, num1), NToTen(n, num2), NToTen(n, ans)
        if (func == '+') and (num1+num2!=ans): 
            check = 0
            break
        if (func == '-') and (num1-num2!=ans): 
            check = 0
            break

    if check: 
        answer_format.append(n)

 

앞서 구한 가장 높은 숫자에서 +1 한 값부터

9진법까지 반복문을 진행해 줍니다.

 

각 숫자들을 10진법으로 변환해서

더하거나 뺀 값이 정답의 10진법 값과 같다면,

그 진법은 유효한 것이 될 겁니다.

 

10진법으로 변환하는 NToTen 함수로 따로 구현해 줬습니다.

 

다 풀고 찾아보니

python에서는 int(string, base) 형태로

문자열을 base의 값 진법으로 변환하는 기능이 있다고 합니다!

 

이제 유효한 진법의 숫자들을 구했다면,

X 값들이 어떤 값들로 나오는지도 찾아봐야겠죠?

 

def TenToN(n, num):
    if num==0: return "0"
    answer = ""

    for idx in range(2,-1,-1):
        div = num // (n**idx)
        if answer or div: answer += str(div)
        num = num % (n**idx)

    return answer

for idx in range(len(answer)):
    num1, func, num2, _, ans = answer[idx].split(" ")
    ans_set = set()
    for a in answer_format:
        num_1, num_2 = NToTen(a, num1), NToTen(a, num2)

        if func=="+": ans_set.add(str(TenToN(a, num_1+num_2)))
        if func=="-": ans_set.add(str(TenToN(a, num_1-num_2)))

    if len(ans_set)==1:
        answer[idx] = ' '.join([num1, func, num2, _, list(ans_set)[0]])
    else: answer[idx] = ' '.join([num1, func, num2, _, "?"])

 

정답 값이 X로 지워진 수식을 모아둔 answer 리스트를 돌면서

찾았던 유효한 진법으로 변환했을 때, 어떤 값이 나오는지

NToTen 함수를 이용하여 구해줍니다.

 

여기서 set 자료구조를 이용하여

구한 지워진 값을 넣어주는데요..!

 

그 이유는 구한 값이 여러 종류라면,

하나의 값으로 딱 정하지 못하는 거겠죠?

 

그럼 우린 그때 "?" 값으로 치환하고

값이 하나로 딱 떨어지는 경우에는

그 값으로 설정해 줄 수 있겠습니다.

 

위의 내용들을 모두 조합해 보면

아래와 같이 작성할 수 있겠네요!

 

def NToTen(n, num):
    if len(num)==1: return int(num)

    number = 0
    for idx in range(len(num)):
        number += int(num[idx])*(n**(len(num)-1-idx))

    return number

def TenToN(n, num):
    if num==0: return "0"
    answer = ""

    for idx in range(2,-1,-1):
        div = num // (n**idx)
        if answer or div: answer += str(div)
        num = num % (n**idx)

    return answer

def solution(expressions):
    answer, answer_format = [], []
    max_format, hint = 0, []
    for e in expressions:
        num1, func, num2, _, ans = e.split(" ")
        
        for idx in range(len(num1)): max_format = max(max_format, int(num1[idx]))
        for idx in range(len(num2)): max_format = max(max_format, int(num2[idx]))
        
        if ans != "X": 
            hint.append(e)
            for idx in range(len(ans)): max_format = max(max_format, int(ans[idx]))
        else: answer.append(e)
    
    for n in range(max_format+1, 10):
        check = 1
        for h in hint:
            num1, func, num2, _, ans = h.split(" ")
            num1, num2, ans = NToTen(n, num1), NToTen(n, num2), NToTen(n, ans)
            if (func == '+') and (num1+num2!=ans): 
                check = 0
                break
            if (func == '-') and (num1-num2!=ans): 
                check = 0
                break
        
        if check: 
            answer_format.append(n)
    
    for idx in range(len(answer)):
        num1, func, num2, _, ans = answer[idx].split(" ")
        ans_set = set()
        for a in answer_format:
            num_1, num_2 = NToTen(a, num1), NToTen(a, num2)

            if func=="+": ans_set.add(str(TenToN(a, num_1+num_2)))
            if func=="-": ans_set.add(str(TenToN(a, num_1-num_2)))
        
        if len(ans_set)==1:
            answer[idx] = ' '.join([num1, func, num2, _, list(ans_set)[0]])
        else: answer[idx] = ' '.join([num1, func, num2, _, "?"])
            
    return answer

 

내용이 길었지만

진법에 대한 이해와 변환하는 과정을

코드로 잘 풀어낼 수 있다면 충분히 풀 수 있었던 문제라는 생각이 듭니다!!

 

끝!