[Python / Java] 백준 10757 - 큰 수 A+B

10757번: 큰 수 A+B

문제 설명

정수 A, B(0 < A,B < 10^10000)를 입력 받아 A+B의 값을 출력한다

 

알고리즘 분류

• 수학
• 구현
• 사칙연산
• 임의 정밀도 / 큰 수 연산

 

풀이 방법

파이썬의 경우, 오버플로우가 발생하지 않으므로 정수의 크기가 10^10000가 되어도 연산이 가능하다.

다만, C, C++, Java 등의 언어의 경우 이러한 큰 수의 경우 연산이 불가하므로 적절히 나누어 계산해야 한다.

재귀함수를 사용하여 풀이하고자 가장 익숙한 파이썬으로 먼저 구현해보려 하였으나 이 과정으로는 반례가 발생하여 올바른 정답을 찾지 못했고, 자바에서 charAt() 메소드를 사용하여 풀이하였다.

---

Python/PyPy3

import sys
A, B=map(int, sys.stdin.readline().split())
print(A+B)

풀이 방법

1. A와 B를 입력 받아 더한다.

---

JAVA

코드 1 - 288ms

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());

		String A=st.nextToken();
		String B=st.nextToken();
		int max=(A.length() > B.length()) ? A.length() : B.length();
		int[] arr=new int[max+1];
		for(int i=0; i<A.length() ; i++) {
			arr[max-A.length()+i+1]=(A.charAt(i)-48);
		}
		for(int i=0; i<B.length() ; i++) {
			arr[max-B.length()+i+1]+=(B.charAt(i)-48);
		}
		for(int j=max; j>0; j--) {
			if(arr[j]/10!=0) {
				arr[j-1]+=arr[j]/10;
				arr[j]=arr[j]%10;
			}
		}
		
		if(!(arr[0]==0)) System.out.print(arr[0]);
		for(int j=1; j<=max; j++) {
			System.out.print(arr[j]);
		}
	}
}

풀이 방법

1. A와 B를 String으로 입력받는다. *int로 입력 받을 경우 오버플로우 발생
2. A와 B 중 더 긴 것의 길이를 max에 저장
3. A와 B를 charAt(0으로 인덱싱하여 각 자리 별 해당하는 숫자를 arr에 저장한다. *charAt()은 int가 아닌 char의 형태로 반환하므로 int로 사용하기 위해서는 48을 빼야 한다. **0 아스키 코드: 48
4. max만큼 arr을 돌며 배열에 10 이상인 숫자가 있을 경우 10으로 나눈 몫을 앞 인덱스에 더하고 나머지는 원래 인덱스에 저장한다.
5. arr 출력

 

코드 2 - 356ms

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());

		String A=st.nextToken();
		String B=st.nextToken();
		
		if(A.length()>B.length()) {
			int[] arr=new int[A.length()+1];
			for(int i=B.length(); i>0 ; i--) {
				arr[A.length()-B.length()+i]+=(A.charAt(A.length()-B.length()+i-1)+B.charAt(i-1)-96);
				arr[A.length()-B.length()+i-1]+=arr[A.length()-B.length()+i]/10;
				arr[A.length()-B.length()+i]%=10;
			}
			for(int i=A.length()-B.length(); i>0; i--) {
				arr[i]+=A.charAt(i-1)-48;
				if (arr[i]>9) {
					arr[i-1]+=arr[i]/10;
					arr[i]%=10;
				}
			}
			if(!(arr[0]==0)) System.out.print(arr[0]);
			for(int j=1; j<=A.length(); j++) {
				System.out.print(arr[j]);
			}
		}
		else {
			int[] arr=new int[B.length()+1];
			for(int i=A.length(); i>0; i--) {
				arr[B.length()-A.length()+i]+=(B.charAt(B.length()-A.length()+i-1)+A.charAt(i-1)-96);
				arr[B.length()-A.length()+i-1]=arr[B.length()-A.length()+i]/10;
				arr[B.length()-A.length()+i]%=10;
			}
			for(int i=B.length()-A.length(); i>0; i--) {
				arr[i]+=B.charAt(i-1)-48;
				if (arr[i]>9) {
					arr[i-1]+=arr[i]/10;
					arr[i]%=10;
				}
			}
			if(!(arr[0]==0)) System.out.print(arr[0]);
			for(int j=1; j<=B.length(); j++) {
				System.out.print(arr[j]);
			}
		}
		
	}
}

코드 1은 A와 B 중 더 긴 값을 찾아 그 크기를 max에 저장한 뒤 연산을 수행했다. 새 변수를 선언하고 초기화하는 것에서 연산 시간을 크게 소모할 것이라고 판단해 코드 2에서는 새 변수를 선언하는 대신 if문으로 A가 더 길 때와 B가 더 길 때로 나누어 연산하였다. 그러나 오히려 if 문을 돌고 max 대신 자잘한 연산 과정을 더 추가한 탓에 훨씬 더 많은 연산 시간을 소모하였다.