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

문제 설명

 

 

10757번: 큰 수 A+B

 

풀이 1 : Fail(정수 오버플로우)

소스 코드

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        char[] A = sc.next().toCharArray(), B = sc.next().toCharArray();
        int maxLength = getMaxLength(A, B), result = 0, mul = 1;
        for (int i = maxLength -1; i > -1; i--) {
            result += (A[i] + B[i] - 96)*mul;
            mul*=10;
        }
        System.out.println(result);
    }

    public static int getMaxLength(char[] A, char[] B){
        int a_length = A.length;
        int b_length = B.length;
        if(a_length > b_length) return a_length;
        else return b_length;
    }
}

 

문제원인 분석

문자열(큰 수) 2개를 입력받아(왜냐하면 큰 수기 때문에) 이를 문자 배열로 변환시켜주고 큰 수 기준 첫째 자리부터 마지막 자리까지 순차적으로 더해주어 결과값을 도출했으나 int, long으로는 이 결과값을 저장할 수 없다.

 

풀이 2 : Success

소스 코드

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        String A = sc.next(), B = sc.next();
        int[] arrA = Arrays.stream(A.split("")).mapToInt(Integer::parseInt).toArray();
        int[] arrB = Arrays.stream(B.split("")).mapToInt(Integer::parseInt).toArray();
        int arrALength = arrA.length, arrBLength = arrB.length;

        int maxLength = getMaxLength(arrALength, arrBLength), sum;
        int[] newArrA = new int[maxLength + 1];
        int[] newArrB = new int[maxLength + 1];
        for (int i = 0; i < arrALength; i++) newArrA[i] = arrA[arrALength - 1 - i];
        for (int i = 0; i < arrBLength; i++) newArrB[i] = arrB[arrBLength - 1 - i];
        for (int i = 0; i < maxLength; i++) {
            sum = newArrA[i] + newArrB[i];
            if(sum >= 10) {
                newArrA[i+1]++;
                newArrA[i] = sum%10;
            }
            else newArrA[i] = sum;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = maxLength; i >= 0; i--) sb.append(newArrA[i]);
        if(sb.charAt(0)=='0') System.out.println(sb.substring(1));
        else System.out.println(sb);
    }

    public static int getMaxLength(int A, int B){
        return A > B ? A : B;
    }
}

 

접근 방법

 

앞선 풀이와 마찬가지로 우선 문자열 2개를 입력받아 이를 정수형 배열로 만들어주었다.

 

정수형 배열의 인덱스는 각 숫자의 자리수를 의미하므로 자리수끼리 더해주기 위함이다. 왜냐하면 숫자로 입력받아 연산하는 것 자체가 불가능한 상황이기 때문에 이처럼 배열을 이용해서 각자리수끼리 더해주는 것이다.

 

두 개의 정수형 배열 중 가장 큰 길이의 배열 길이(maxLength)를 구한 후 이 새로운 배열의 길이로 새로운 정수형 배열 2개를 초기화 시켜주었다. 이때 새로운 배열의 길이 보다 1 더 큰 수로 길이를 정해주었는데, 이는 각 자릿 수끼리 더할 때 carry(자리올림 수)가 발생하기 때문이다.

 

또한 기존 정수형 배열을 이용해 새롭게 생성된 정수형 배열에 반대 순서로(reverse) 값을 입력시켜주도록 했는데, 이는 리틀 엔디안 방식으로 더해주어야 덧셈 연산이 용이하기 때문이다.

 

새롭게 정렬된 두 개의 배열 각 자릿수별로 덧셈 연산을 진행했는데, 임의의 배열(여기서는 newArrA)에 더한 값을 저장하고 carry(자리올림 수)가 발생하면 이를 다음 인덱스 값으로 저장시켜주도록 했다.

 

최종적으로 모든 연산이 마무리된 newArrA 배열의 요소값들을 다시 반대 순서로(앞서 reverse 했으닌까) StringBuilder 객체에 append 시켜주도록 했다.

 

다만, 마지막 자리수 연산에서 carry가 발생하지 않는 경우 첫번째 문자가 0으로 남기 때문에 첫번째 문자가 0일 경우 substring을 통해 인덱스 1부터의 문자열을 출력시키도록 했다.

 

풀이 3 : Success

소스 코드

import java.math.BigInteger;
import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        BigInteger A = new BigInteger(sc.next()), B = new BigInteger(sc.next());
        System.out.println(A.add(B));
    }
}​

 

접근 방법

BigInteger 객체를 이용하면 손 쉽게 풀 수 있다. 이때 풀이 2(BigInteger을 이용하지 않은 방법)와 풀이 3(BigInteger을 이용한 방법)간 성능 차이는 크지 않았다.

 

(아래 결과) 풀이 2 (위 결과) 풀이 1

 

참고 자료

• https://st-lab.tistory.com/199
• https://www.acmicpc.net/problem/10757