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

https://www.acmicpc.net/problem/10757

10757번: 큰 수 A+B

---

---

알고리즘

1. 문제

• long 타입 범위 : (-2⁶³) ~ (2⁶³ - 1)
• 문제 내의 주어진 범위 : 10¹⁰⁰⁰⁰ ➡ long 타입 범위 초과

---

2. 방법

2.1. 덧셈 과정 직접 구현

[예시]

[각 자리수]

• 10으로 나눈 나머지 값 저장
• 10이 넘을 경우 올림 발생 ➡ 다음 자리수에 +1

2.2. Java의 BigInteger 클래스 활용

• BigInteger : 클래스 객체 ➡ 선언 및 생성 필수
• Big Integer 생성 시 파라미터로 문자열 넘겨줘야 함

---

3. 구현 방법

• Scanner + 직접 구현
• Scanner + BigInteger
• BufferedReader + 직접 구현
• BufferedReader + BigInteger

---

풀이

1. Scanner + 직접 구현

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
		
        Scanner in = new Scanner(System.in);
		
        String str_A = in.next();
        String str_B = in.next();
		
        //두 개의 수 중 가장 긴 자리수 길이 구하기
        int max_length = Math.max(str_A.length(), str_B.length());
		
        //마지막 자리수 올림이 있을 경우 대비 + 1
        int[] A = new int[max_length + 1];
        int[] B = new int[max_length + 1]; 
 
        //A 초기화
        for(int i = str_A.length() - 1, idx = 0; i >= 0; i--, idx++) {
            //맨 뒤 문자부터 역순으로 하나씩 저장
            A[idx] = str_A.charAt(i) - '0';
        }
		
        //B 초기화
        for(int i = str_B.length() - 1, idx = 0; i >= 0; i--, idx++) {
            //맨 뒤 문자부터 역순으로 하나씩 저장
            B[idx] = str_B.charAt(i) - '0';
        }
		
        //덧셈
        for(int i = 0; i < max_length; i++) {
            int value = A[i] + B[i];
            A[i] = value % 10; //더한 값을 10으로 나눈 나머지 값 저장
            A[i + 1] += (value / 10); //올림값 = 더한 값을 10으로 나눈 몫
        }
		
        // A 배열 역순 출력
        // 가장 높은 자리수가 0일 수도 있기 때문에 0이 아닐 경우에만 출력
        StringBuilder sb = new StringBuilder();
        
        /*
        배열 각 원소의 마지막 덧셈에서 올림 발생하면
        초기화된 A의 가장 끝 값이 0이 아니게 됨
        ∴ 그 때만 배열 끝에 올림된 결과값 추가
        ➡ 결과값의 제일 첫 번째 자리에 해당 값 추가
        */
        if(A[max_length] != 0) {
            sb.append(A[max_length]);
        }
        /*
        A 배열에서 각 원소를 max_length - 1 범위만큼 역순으로 출력
        */
        for(int i = max_length - 1; i >= 0; i--) {
            sb.append(A[i]);
        }
        System.out.println(sb);
    }
}

 

2. Scanner + BigInteger

import java.util.Scanner;
import java.math.BigInteger;
 
public class Main {
    public static void main(String[] args) {
		
        Scanner in = new Scanner(System.in);
		
        BigInteger A = new BigInteger(in.next());
        BigInteger B = new BigInteger(in.next());
		
        A = A.add(B);
		
        System.out.println(A.toString()); //문자열화
    }
}

---

3. BufferedReader + 직접 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
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 str_A = st.nextToken();
        String str_B = st.nextToken();
		
        //두 개의 수 중 가장 긴 자리수 길이 구하기
        int max_length = Math.max(str_A.length(), str_B.length());
		
        //마지막 자리수 올림이 있을 경우 대비 + 1
        int[] A = new int[max_length + 1];
        int[] B = new int[max_length + 1];
 
        //A 초기화
        for(int i = str_A.length() - 1, idx = 0; i >= 0; i--, idx++) {
            //맨 뒤 문자부터 역순으로 하나씩 저장
            A[idx] = str_A.charAt(i) - '0';
        }
		
        //B 초기화
        for(int i = str_B.length() - 1, idx = 0; i >= 0; i--, idx++) {
            //맨 뒤 문자부터 역순으로 하나씩 저장
            B[idx] = str_B.charAt(i) - '0';
        }
		
        //덧셈
        for(int i = 0; i < max_length; i++) {
            int value = A[i] + B[i];
            A[i] = value % 10; //더한 값을 10으로 나눈 나머지 값 저장
            A[i + 1] += (value / 10); //올림값 = 더한 값을 10으로 나눈 몫
        }
		
        // A 배열 역순 출력
        // 가장 높은 자리수가 0일 수도 있기 때문에 0이 아닐 경우에만 출력
        StringBuilder sb = new StringBuilder();
        
        /*
        배열 각 원소의 마지막 덧셈에서 올림 발생하면
        초기화된 A의 가장 끝 값이 0이 아니게 됨
        ∴ 그 때만 배열 끝에 올림된 결과값 추가
        ➡ 결과값의 제일 첫 번째 자리에 해당 값 추가
        */
        if(A[max_length] != 0) {
            sb.append(A[max_length]);
        }
        /*
        A 배열에서 각 원소를 max_length - 1 범위만큼 역순으로 출력
        */
        for(int i = max_length - 1; i >= 0; i--) {
            sb.append(A[i]);
        }
        System.out.println(sb);
    }
}

 

4. BufferedReader + BigInteger

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.math.BigInteger;
 
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(), " ");
		
        BigInteger A = new BigInteger(st.nextToken());
        BigInteger B = new BigInteger(st.nextToken());
		
        A = A.add(B);
		
        System.out.println(A.toString()); //문자열화
    }
}

---

성능

1. BufferedReader + 직접 구현
2. Scanner + 직접 구현
3. BufferedReader + BigInteger
4. Scanner + BigInteger

 

---

출처 : https://st-lab.tistory.com/199