728x90
😉 아이디어
1. _!expressions!_ digit 중 가장 큰 숫자를 선별하고 +1 해주어 2~9 진수 중 반복 단위를 최소화
2. 예상 진수를 순회하며 _!10진수!_로 변환하고 값이 일치하는지 확인(X가 없는 계산식에만 적용)
3. 주어진 식을 모두 일치시키면 _!candidates!_ 변수에 후보군으로 저장
4. _!candidates!_ 변수를 순회하며 X가 있는 값들을 계산, 단 이전 후보군과의 계산 결과가 다르면 _!?!_로 표기
😉 풀이
def solution(expressions):
answer = []
non_x_exprs = []
x_exprs = []
exprs = []
for expression in expressions:
exprs.append(expression.split(" "))
if 'X' in expression:
x_exprs.append(expression.split(" "))
else:
non_x_exprs.append(expression.split(" "))
min_base = get_minimum_base(exprs)
candidates = get_base_candidates(non_x_exprs, min_base)
guessed_values = guess_values(x_exprs, candidates)
for i in range(len(x_exprs)):
x_exprs[i][-1] = str(guessed_values[i])
answer.append(" ".join(x_exprs[i]))
return answer
def guess_values(exprs, candidates):
converted_values = [-1] * len(exprs)
for candidate in candidates:
for i, expression in enumerate(exprs):
left_num, operator, right_num, _, result = expression
decimal_left_num = int(str(left_num), candidate)
decimal_right_num = int(str(right_num), candidate)
calc_result = -1
if operator == '+':
calc_result = convert_to_base(decimal_left_num + decimal_right_num, candidate)
else:
calc_result = convert_to_base(decimal_left_num - decimal_right_num, candidate)
if converted_values[i] == -1:
converted_values[i] = calc_result
else:
if converted_values[i] != calc_result:
converted_values[i] = '?'
return converted_values
def get_base_candidates(exprs, min_base):
candidates = []
for i in range(min_base, 10):
is_valid_base = True
for expression in exprs:
left_num, operator, right_num, _, result = expression
decimal_left_num = int(left_num, i)
decimal_right_num = int(right_num, i)
decimal_result_num = int(result, i)
# print(f'left = {decimal_left_num}, right = {decimal_right_num}, result = {decimal_result_num}')
if operator == '+':
if decimal_left_num + decimal_right_num != decimal_result_num:
is_valid_base = False
else:
if decimal_left_num - decimal_right_num != decimal_result_num:
is_valid_base = False
if is_valid_base:
candidates.append(i)
return candidates
def get_minimum_base(exprs):
max_digit = 0
for expression in exprs:
left_num, operator, right_num, _, result = expression
for idx in range(len(left_num)):
max_digit = max(max_digit, int(left_num[idx]))
for idx in range(len(right_num)):
max_digit = max(max_digit, int(right_num[idx]))
if result != "X":
for idx in range(len(result)):
max_digit = max(max_digit, int(result[idx]))
return max_digit + 1
def convert_to_base(decimal_number, base):
if decimal_number == 0:
return 0
reversed_base_digits = ''
while decimal_number > 0:
decimal_number, remainder = divmod(decimal_number, base)
reversed_base_digits += str(remainder)
return reversed_base_digits[::-1]✔️ 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/340210
