풀이 전략은 다음과 같습니다.
두 정수 A와 B의 크기가 매우 크네요!
단순히 A + B를 print하게 되면 시간 초과가 발생합니다.
그렇다면 어떤 방법을 사용하면 될까요?
일의 자리부터 두 수의 같은 자리끼리 더하고
더한 값이 10이 넘어가면 carry flag를 만들어 다음 자리 수와 같이 더하는 방법을 사용하면 됩니다.
carry flag는 flag 변수에 저장하고, flag는 0으로 초기화해주었습니다.
일의 자리를 더하는 상황에서 carry flag는 항상 0이기 때문입니다.
제일 큰 자리부터 스택에 저장하면, 스택의 top에는 항상 덧셈의 대상이 되는 수가 놓여집니다. 따라서 A와 B의 자리수들을 스택에 저장하고, carry flag와 스택의 top끼리 더해주면 됩니다.
정수 A와 B의 자리 수가 다를 수 있기 때문에
A 혹은 B의 스택이 비어있다면 0을 추가로 push해주었습니다.
A, B = input().split()
stack_A = [a for a in A] # A를 스택에 저장
stack_B = [b for b in B] # B를 스택에 저장
flag = 0 # carry flag
ans = ""
while True:
if len(stack_A) == 0 and len(stack_B) == 0:
if flag != 0: # 남아있는 carry flag 있다면
ans = str(flag) + ans
print(ans)
break
elif len(stack_A) == 0: # stack_A가 빈 스택이라면
stack_A.append(0)
elif len(stack_B) == 0: # stack_B가 빈 스택이라면
stack_B.append(0)
a = int(stack_A.pop())
b = int(stack_B.pop())
sumAB = flag + a + b
ans = str(sumAB % 10) + ans
flag = sumAB // 10 # 새로운 carry flag 저장
