반응형
Python을 이용하여 '?' 문자가 포함된 수식을 복원하는 문제를 해결하는 방법을 설명하겠습니다. 이 문제는 수식에서 '?' 문자를 적절한 숫자로 대체하여 올바른 결과를 얻는 것이 목표입니다. 이를 해결하기 위해 작성한 Python 코드를 소개하고, 각 부분이 어떻게 동작하는지 자세히 설명하겠습니다.
문제 설명
주어진 문제는 다음과 같습니다:
- 수식 형태: A + B = C
- A, B, C에는 0-9 사이의 숫자와 '?' 문자가 포함되어 있습니다.
- '?' 문자를 적절한 숫자로 바꾸어 올바른 수식을 복원해야 합니다.
예를 들어, 입력이 ?2 + 3? = 55라면, 42 + 13 = 55와 같은 형태로 '?'를 대체해야 합니다.
코드 설명
다음은 문제를 해결하기 위해 작성한 Python 코드입니다.
def c2i(c):
# 문자 c를 정수로 변환, '?'이면 -1 반환
if c == '?':
return -1
return ord(c) - ord('0')
def candidate(a_in, b_in, c_in, carry_in, carry_out):
ret = []
# a_in, b_in, c_in이 -1이면 각각 0-9 범위의 값, 아니면 해당 값을 사용
alist = range(10) if a_in == -1 else [a_in]
blist = range(10) if b_in == -1 else [b_in]
clist = range(10) if c_in == -1 else [c_in]
# 가능한 (a, b, c) 조합을 모두 탐색
for a in alist:
for b in blist:
for c in clist:
# a + b + carry_in - c == 10 * carry_out을 만족하는 조합만 추가
if a + b + carry_in - c == 10 * carry_out:
ret.append((a, b, c))
return ret
def val_list(L):
# 리스트 L이 비어있으면 -1 반환, 아니면 정수로 변환하여 반환
if not L:
return -1
return int("".join(map(str, L[::-1])))
def solve():
S = input().strip() # 입력 문자열 받기
Astr, S = S.split('+') # '+' 기준으로 나누기
Bstr, Cstr = S.split('=') # '=' 기준으로 나누기
# 각 문자열을 뒤집기 (자릿수 계산을 위해)
Astr, Bstr, Cstr = Astr[::-1], Bstr[::-1], Cstr[::-1]
len_op = max(len(Astr), len(Bstr)) # 가장 긴 문자열의 길이
notzeroA = len(Astr) - 1 if len(Astr) > 1 else -1 # A의 0이 아닌 자리 인덱스
notzeroB = len(Bstr) - 1 if len(Bstr) > 1 else -1 # B의 0이 아닌 자리 인덱스
# 길이를 len_op로 맞추기 위해 '0'으로 패딩
Astr = Astr.ljust(len_op, '0')
Bstr = Bstr.ljust(len_op, '0')
# 각 자리수를 정수 리스트로 변환
AA, BB, CC = map(lambda x: list(map(c2i, x)), [Astr, Bstr, Cstr])
# C의 길이가 적절하지 않으면 -1 출력
if len(CC) not in (len_op, len_op + 1):
print(-1)
return
def update_max(A_mx, B_mx, C_mx, A_tmp, B_tmp, C_tmp):
# C_tmp가 C_mx보다 크거나 (C_tmp == C_mx이고 A_tmp가 A_mx보다 크면)
# A_mx, B_mx, C_mx를 A_tmp, B_tmp, C_tmp로 업데이트
if val_list(C_tmp) > val_list(C_mx) or (val_list(C_tmp) == val_list(C_mx) and val_list(A_tmp) > val_list(A_mx)):
return A_tmp[:], B_tmp[:], C_tmp[:]
return A_mx, B_mx, C_mx
# 초기화
Ac, Bc, Cc, An, Bn, Cn = [], [], [], [], [], []
# 각 자리수에 대해 처리
for digit in range(len_op):
# 이전 단계의 리스트 복사
An_before, Bn_before, Cn_before = An[:], Bn[:], Cn[:]
Ac_before, Bc_before, Cc_before = Ac[:], Bc[:], Cc[:]
# 현재 단계에서의 최대값 초기화
An_mx, Bn_mx, Cn_mx = [], [], []
Ac_mx, Bc_mx, Cc_mx = [], [], []
# An의 길이가 현재 자릿수와 같으면 (즉, 아직 계산 중인 경우)
if len(An) == digit:
# carry_out이 0 또는 1인 경우에 대해 가능한 조합 탐색
for carry_out in range(2):
cand = candidate(AA[digit], BB[digit], CC[digit], 0, carry_out)
for val in cand:
# 0이 아닌 자리에서 0을 사용하지 않도록 필터링
if notzeroA == digit and val[0] == 0:
continue
if notzeroB == digit and val[1] == 0:
continue
if carry_out == 0:
# carry_out이 0인 경우 최대값 업데이트
An_mx, Bn_mx, Cn_mx = update_max(An_mx, Bn_mx, Cn_mx,
An_before[:] + [val[0]], Bn_before[:] + [val[1]], Cn_before[:] + [val[2]])
else:
# carry_out이 1인 경우 최대값 업데이트
Ac_mx, Bc_mx, Cc_mx = update_max(Ac_mx, Bc_mx, Cc_mx,
An_before[:] + [val[0]], Bn_before[:] + [val[1]], Cn_before[:] + [val[2]])
# Ac의 길이가 현재 자릿수와 같고 자릿수가 0이 아닌 경우
if len(Ac) == digit and digit != 0:
# carry_out이 0 또는 1인 경우에 대해 가능한 조합 탐색
for carry_out in range(2):
cand = candidate(AA[digit], BB[digit], CC[digit], 1, carry_out)
for val in cand:
# 0이 아닌 자리에서 0을 사용하지 않도록 필터링
if notzeroA == digit and val[0] == 0:
continue
if notzeroB == digit and val[1] == 0:
continue
# 최대값 업데이트
Ac_mx, Bc_mx, Cc_mx = update_max(Ac_mx, Bc_mx, Cc_mx,
Ac_before[:] + [val[0]], Bc_before[:] + [val[1]], Cc_before[:] + [val[2]])
# 현재 단계에서의 최대값으로 리스트 업데이트
Ac, Bc, Cc = Ac_mx, Bc_mx, Cc_mx
An, Bn, Cn = An_mx, Bn_mx, Cn_mx
# 결과 처리
if len(CC) == len_op + 1:
# C의 길이가 len_op + 1인 경우
if CC[len_op] not in (-1, 1) or len(Ac) != len_op:
print(-1)
return
Cc.append(1)
print(f"{val_list(Ac)}+{val_list(Bc)}={val_list(Cc)}")
return
if len(An) != len_op:
print(-1)
return
print(f"{val_list(An)}+{val_list(Bn)}={val_list(Cn)}")
if __name__ == "__main__":
solve()
코드 동작 원리
- 입력 받기: 사용자로부터 수식을 입력받고, +와 =를 기준으로 각각 A, B, C 부분을 나눕니다.
- 문자열 뒤집기: 계산을 편리하게 하기 위해 각 부분 문자열을 뒤집습니다.
- 최대 길이 설정: A와 B의 최대 길이를 구하여, 짧은 문자열의 경우 오른쪽에 0을 추가하여 길이를 맞춥니다.
- 문자 -> 숫자 변환: 각 문자열을 숫자로 변환하는 함수 c2i를 이용하여 A, B, C를 리스트로 변환합니다.
- 길이 검증: C의 길이가 적절한지 검증하고, 적절하지 않다면 -1을 출력하고 종료합니다.
- 최대 값 갱신: 후보를 확인하고, 현재까지의 최대 값을 갱신하는 함수 update_max를 정의합니다.
- 수식 복원: 각 자리수마다 가능한 값을 확인하고, A와 B에 적절한 숫자를 배정하여 C를 만족시키는 조합을 찾습니다.
- 결과 출력: 복원된 수식을 출력합니다.
반응형
'코딩 > 백준-알고리즘' 카테고리의 다른 글
[백준] 1144 싼 비용 Python 3 (0) | 2024.06.10 |
---|---|
[백준] 5257 timeismoney Python 3 (0) | 2024.06.05 |
[백준] 4008 특공대 Python 3 (0) | 2024.05.30 |
[백준] 1031 스타대결 Python 3 (0) | 2024.05.29 |
[백준] 5979 남땜하기 C++ (Feat 고찰) (0) | 2024.05.28 |