Baekjoon10757: 큰 수 A + B

문제

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. (0 < A,B < 10^10000)

출력

첫째 줄에 A+B를 출력한다.

 

추상화

10의 10000승은 엄청 크다. 길이를 보았을 때 숫자형을 이용할 수는 없다고 보았다
문자열을 통한 연산을 구현한다

1) 처음에는 단순히 길이가 큰 쪽에 작은 쪽을 더하고 각 자리의 합이 10을 넘으면 윗 자리 값에 1을 추가하는 것을 생각했다
            예시)                 12848214912492
                                       +       123124043
→length가 작은 곳을 기준으로 계산한다

2) 그러나 앞자리가 연쇄적으로 바뀔 때 문제가 생긴다
            예시)                 9999999999999
                                      +                         1

3) 2번을 극복하기 위해 각 자리의 수를 맞춘다
            예시)                 9999999999999
                                  + 0000000000001

4) 뒤에서 먼저 계산하고 앞으로 붙인다
배열을 사용해 연산할 수 있지만 지금까지 배열을 쭉 사용해왔기 때문에 다른 방법을 탐색해본다
→깔끔하게 계산하기 위해 StringBuilder로 앞에서부터 출력한 뒤 뒤집는다(reverse)

import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException{
	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	 StringBuilder A = new StringBuilder();
	 StringBuilder B = new StringBuilder();
	 StringBuilder Sum = new StringBuilder();
//Sum은 값을 계산할 곳
	 int a=0;
	 int b=0;
	 int c =0;
//a, b, c는 반복문 안에서 각 자리수의 숫자를 가져오는 변수
	 boolean upper = false;
// 각 자리수의 합이 10이 넘으면 upper값이 켜지고 다음 자리수가 1 올라간다
	 StringTokenizer st = new StringTokenizer(br.readLine(), " ");
	 A.append(st.nextToken()).reverse();
	 B.append(st.nextToken()).reverse();
	 int lengthA = A.length();
	 int lengthB = B.length();
	 int gap = lengthA-lengthB;
	 int length; //더 큰 길이를 가져온다
	 if(gap>=0) {
		for(int i=0; i<gap;i++) {
			B.append("0");
		}
		 length = lengthA;
	 }else {
		 for(int i=0; i<-1*gap;i++) {
			 A.append("0");
		 }
		 length = lengthB;
	 }
//길이가 더 짧은 곳에 0을 붙여주어 길이를 맞춘다
	 for(int i=0; i<length; i++) {
		 a= Character.getNumericValue(A.toString().charAt(i));
		 b= Character.getNumericValue(B.toString().charAt(i));
		 c= a+b;
		 if(upper==true) {
			 c ++;
			 upper = false;
		 }
//이전 계산에서 10이 넘었으면 이번 자리수에서 1을 더한다
		 if(c>=10) {
			 c -=10;
			 upper = true;
		 }
		 Sum.append(c);
	 }
	 if(upper==true) {
		 Sum.append(1);
	 }
//끝자리에서 값이 10을 넘었다면 1을 추가해준다
	 System.out.println(Sum.reverse().toString());
//계산한 값을 뒤집어서 출력한다
}	 
}

 

배열을 이용한 풀이

import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException{
	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	 int[] A = new int[10001];
	 int[] B = new int[10001];
	 StringBuilder Sum = new StringBuilder();
	 int lengthA, lengthB, length;
	 boolean upper = false;
//길이를 받아줄 변수들을 미리 생성
//A와 B의 배열을 만든다 배열 번호나 자리수 올림 등 일단 10001개로 한다
	 String a,b;
	 StringTokenizer st = new StringTokenizer(br.readLine(), " ");
	 a = st.nextToken();
	 b = st.nextToken();
	 lengthA = a.length();
	 lengthB = b.length();
	 for(int i=0; i<lengthA; i++) {
		 A[lengthA-i-1] = Character.getNumericValue(a.charAt(i));
//문자열을 받는 동시에 0번부터 문자길이까지 각각 숫자를 거꾸로 배치한다
	 }
	 for(int i=0; i<lengthB; i++) {
		 B[lengthB-i-1] = Character.getNumericValue(b.charAt(i));
	 }
	 if(lengthA>=lengthB) {
		 length = lengthA;
	 } else { length = lengthB;}
//더 긴 길이를 가져온다
	 for(int i=0; i<length; i++) {
		 A[i] = A[i]+B[i];
	 }
//두 배열을 더한다
	 for(int i=0; i<length; i++) {
		 if(upper == true) {
			 A[i] ++;
			 upper = false;
		 }
		 if(A[i]>=10) {
			 upper = true;
			 A[i] -=10;
		 }
	 }
//배열의 최대 길이까지만 연산한다
	for(int i=0; i<length;i++) {
		Sum.append(A[i]);
	}
//연산한 곳까지 StringBuilder에 추가
	if(upper == true) {
		Sum.append(1);
	}
//upper가 켜져있으면 뒤에 1을 추가한다
	System.out.print(Sum.reverse().toString());
//뒤집어서 출력한다
}
}

*메모리가 많이 줄었음을 확인할 수 있다