문제 설명
당신은 덧셈 혹은 뺄셈 수식이 여러 개 적힌 고대 문명의 유물을 찾았습니다. 이 수식들을 관찰하던 당신은 이 문명이 사용하던 진법 체계가 10진법이 아니라는 것을 알아냈습니다. (2 ~ 9진법 중 하나입니다.)
수식들 중 몇 개의 수식은 결괏값이 지워져 있으며, 당신은 이 문명이 사용하던 진법에 맞도록 지워진 결괏값을 채워 넣으려 합니다.
다음은 그 예시입니다.
<수식>
14 + 3 = 17
13 - 6 = X
51 - 5 = 44
- X로 표시된 부분이 지워진 결괏값입니다.
51 - 5 = 44에서 이 문명이 사용하던 진법이 8진법임을 알 수 있습니다. 따라서 13 - 6 = X의 지워진 결괏값을 채워 넣으면 13 - 6 = 5가 됩니다.
다음은 또 다른 예시입니다.
<수식>
1 + 1 = 2
1 + 3 = 4
1 + 5 = X
1 + 2 = X
주어진 수식들에서 이 문명에서 사용한 진법이 6 ~ 9진법 중 하나임을 알 수 있습니다.
1 + 5 = X의 결괏값은 6진법일 때 10, 7 ~ 9진법일 때 6이 됩니다. 이와 같이 결괏값이 불확실한 수식은 ?를 사용해 1 + 5 = ?와 같이 결괏값을 채워 넣습니다.
1 + 2 = X의 결괏값은 6 ~ 9진법에서 모두 3으로 같습니다. 따라서 1 + 2 = X의 지워진 결괏값을 채워 넣으면 1 + 2 = 3이 됩니다.
덧셈 혹은 뺄셈 수식들이 담긴 1차원 문자열 배열 expressions가 매개변수로 주어집니다. 이때 결괏값이 지워진 수식들의 결괏값을 채워 넣어 순서대로 문자열 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 2 ≤ expressions의 길이 ≤ 100
입출력 예
| expressions | result |
| ["14 + 3 = 17", "13 - 6 = X", "51 - 5 = 44"] | ["13 - 6 = 5"] |
| ["1 + 1 = 2", "1 + 3 = 4", "1 + 5 = X", "1 + 2 = X"] | ["1 + 5 = ?", "1 + 2 = 3"] |
| ["10 - 2 = X", "30 + 31 = 101", "3 + 3 = X", "33 + 33 = X"] | ["10 - 2 = 4", "3 + 3 = 10", "33 + 33 = 110"] |
| ["2 - 1 = 1", "2 + 2 = X", "7 + 4 = X", "5 - 5 = X"] | ["2 + 2 = 4", "7 + 4 = ?", "5 - 5 = 0"] |
| ["2 - 1 = 1", "2 + 2 = X", "7 + 4 = X", "8 + 4 = X"] | ["2 + 2 = 4", "7 + 4 = 12", "8 + 4 = 13"] |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
문제 예시와 같습니다.
입출력 예 #3
30 + 31 = 101에서 이 문명이 사용하던 진법이 6진법임을 알 수 있습니다. 따라서 10 - 2 = X, 3 + 3 = X, 33 + 33 = X의 지워진 결괏값을 채워 넣으면 10 - 2 = 4, 3 + 3 = 10, 33 + 33 = 110이 됩니다.
따라서 ["10 - 2 = 4", "3 + 3 = 10", "33 + 33 = 110"]을 return 해야 합니다.
입출력 예 #4
수식에 등장하는 숫자들을 통해 이 문명이 사용하던 진법이 8진법 혹은 9진법임을 알 수 있습니다. 2 + 2 = X와 5 - 5 = X의 지워진 결괏값을 채워 넣으면 8진법, 9진법에 관계없이 2 + 2 = 4, 5 - 5 = 0이 됩니다. 7 + 4 = X의 결괏값은 불확실하므로 지워진 결괏값을 채워 넣으면 7 + 4 = ?가 됩니다.
따라서 ["2 + 2 = 4", "7 + 4 = ?", "5 - 5 = 0"]을 return 해야 합니다.
입출력 예 #5
네 번째 예시와 같지만 5 - 5 = X가 8 + 4 = X로 바뀌었습니다. 이 문명이 사용하던 진법이 9진법임을 알 수 있으므로 7 + 4 = X와 8 + 4 = X의 지워진 결괏값을 채워 넣으면 7 + 4 = 12, 8 + 4 = 13이 됩니다.
따라서 ["2 + 2 = 4", "7 + 4 = 12", "8 + 4 = 13"]을 return 해야 합니다.
풀이 :
이 문제는 구현 문제이다.
일단 최소한을 돌기 위해서 주어진 식에서 가장 큰 숫자를 찾아주었고
그 다음 숫자부터 진법이 들어가게한다.
int 함수를 사용하면 int("10",진수) 넣어주면 저절로 계산이 된다.
1. 73.9 점
from collections import defaultdict
# 10진수 값을 base 진법으로 변환하는 함수
def to_base(n, base):
if n == 0:
return "0"
digits = []
while n > 0:
digits.append(str(n % base))
n //= base
return ''.join(digits[::-1])
def valid_result(base, expression):
# expression을 공백으로 분리
ls = expression.split(" ")
a = int(ls[0], base) # 첫 번째 숫자
b = int(ls[2], base) # 두 번째 숫자
operator = ls[1] # 연산자
# 결과 값이 X인 경우 (X 값을 구해야 하는 상황)
if ls[4] == "X":
if operator == "+":
result = a + b
elif operator == "-":
result = a - b
return to_base(result, base) # 계산 결과를 base 진법으로 변환하여 반환
# 결과 값이 주어진 경우 (정답 검증)
else:
c = int(ls[4], base) # 결과 값
if operator == "+" and a + b == c:
return base
elif operator == "-" and a - b == c:
return base
return False
def solution(expressions):
number_stk = []
calculate_stk = []
number = ""
incorrect_expression = []
correct_expression = []
# 시작 할 base 값 구하기
for expression in expressions:
if "X" in expression:
incorrect_expression.append(expression)
else:
correct_expression.append(expression)
express, res = expression.replace(" ", "").split("=")
if res != "X":
number += res
for i in express:
if i == "+" or i == "-":
calculate_stk.append(i)
else:
number_stk.append(i)
number += i
number = sorted(number, key=lambda x: -int(x[0]))
start_base = int(number[0]) + 1
# 뭐가 될지 찾아야함.
possible_base = defaultdict(list)
for expression in correct_expression:
for base in range(start_base, 10):
valid = valid_result(base, expression)
if valid:
possible_base[expression].append(valid_result(base, expression))
if len(possible_base) >= 1:
common_bases = set(possible_base[next(iter(possible_base))]) # 첫 번째 키의 값을 기준으로 초기화
for bases in possible_base.values():
common_bases.intersection_update(bases) # 교집합 업데이트
set_possible_base = sorted(list(common_bases))
answer = []
for incorrect_express in incorrect_expression:
sets = set()
for possible_base in set_possible_base:
sets.add(valid_result(possible_base, incorrect_express))
temp = str(sets.pop()) if len(sets) == 1 else '?'
answer.append(incorrect_express[:-1] + temp)
return answer
print(solution(["14 + 3 = 18"]))
# print(solution(["1 + 1 = 2", "1 + 3 = 4", "1 + 5 = X", "1 + 2 = X"]))
# print(solution(["10 - 2 = X", "30 + 31 = 101", "3 + 3 = X", "33 + 33 = X"]))
# print(solution(["2 - 1 = 1", "2 + 2 = X", "7 + 4 = X", "5 - 5 = X"]))
# print(solution(["2 - 1 = 1", "2 + 2 = X", "7 + 4 = X", "8 + 4 = X"]))
뒤에 6~7개 정도가 시간초과가 나는데
생각해보니 길이가 0 일때 런타임 에러가 터지는 것 같다.
정
# 10진수 값을 base 진법으로 변환하는 함수
def to_base(n, base):
if n == 0:
return "0"
digits = []
while n > 0:
digits.append(str(n % base))
n //= base
return ''.join(digits[::-1])
def valid_result(base, expression):
# expression을 공백으로 분리
ls = expression.split(" ")
a = int(ls[0], base) # 첫 번째 숫자
b = int(ls[2], base) # 두 번째 숫자
operator = ls[1] # 연산자
# 결과 값이 X인 경우 (X 값을 구해야 하는 상황)
if ls[4] == "X":
if operator == "+":
result = a + b
elif operator == "-":
result = a - b
return to_base(result, base) # 계산 결과를 base 진법으로 변환하여 반환
# 결과 값이 주어진 경우 (정답 검증)
else:
c = int(ls[4], base) # 결과 값
if operator == "+" and a + b == c:
return base
elif operator == "-" and a - b == c:
return base
return False
def solution(expressions):
number_stk = []
calculate_stk = []
number = ""
incorrect_expression = []
correct_expression = []
# 시작 할 base 값 구하기
for expression in expressions:
if "X" in expression:
incorrect_expression.append(expression)
else:
correct_expression.append(expression)
express, res = expression.replace(" ", "").split("=")
if res != "X":
number += res
for i in express:
if i == "+" or i == "-":
calculate_stk.append(i)
else:
number_stk.append(i)
number += i
number = sorted(number, key=lambda x: -int(x[0]))
start_base = int(number[0]) + 1
# 뭐가 될지 찾아야함.
answer_list = []
for n in range(start_base, 10):
temp = 1
for correct in correct_expression:
x = valid_result(n, correct)
if not x:
temp = 0
if temp:
answer_list.append(n)
answer_list = list(set(answer_list))
answer = []
for incorrect_express in incorrect_expression:
sets = set()
for possible_base in answer_list:
sets.add(valid_result(possible_base, incorrect_express))
temp = str(sets.pop()) if len(sets) == 1 else '?'
answer.append(incorrect_express[:-1] + temp)
return answer
answer_list 부분을 바꾸어 주었다.
원래는 각 식 마다 가능한 숫자들을 디폴트 딕에 담았지만 이번에는 모든 식에서 가능한 숫자들을 담는 식으로 했고.
set과 list로 범위를 줄여주었다.
댓글