[백준알고리즘/기본 수학 1단계] 10757번 문제 : 큰 수 A+B

안녕하세요

백준 알고리즘 단계별로 풀어보기 8단계 10757번 문제 큰수 A+B를 풀어봤습니다

이번 문제는 BigInteger를 사용하면 간단하게 풀 수는 있습니다

하지만 시간이... 시간을 줄이려면 알고리즘을 만들어 풀어야합니다

제가 풀은 방법에 대해서 설명해보겠습니다!

 

---

문제 링크입니다

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

10757번: 큰 수 A+B

 

문제

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

 

입력

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

 

출력

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

 

 

---

 

 

문제 풀이

첫 번째 방법

BigInteger를 사용하여 문제를 풀었습니다

값을 받아 BigInteger로 변환해 더해주면 끝입니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		// BufferedReader 및 StringTokenizer 선언 및 입력 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		// BigInterger 선언 및 a + b
		BigInteger a = new BigInteger(st.nextToken());
		BigInteger b = new BigInteger(st.nextToken());
		a = a.add(b);
		
		System.out.println(a); // 결과 출력
	}
}

 

---

 

두 번째 방법

String[] 배열로 만들어서 반복문을 사용 마지막 배열부터 하나씩 더해줍니다

전부 더해준 후 reverse()를 사용하여 결과를 출력합니다

설명이 힘드므로 예제를 참고바랍니다!

알고리즘을 이용해 맨 처음 풀은 방법이라 속도가 많이 느리게 나왔습니다...

이런 방법도 있구나 참고만 바랍니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		// BufferedReader, StringTokenizer, StringBuilder 선언 및 입력 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		StringBuilder sb = new StringBuilder();
							
		// Split을 사용 -> a, b 입력
		String[] a = st.nextToken().split("");
		String[] b = st.nextToken().split("");
		
		// Count, 10이상 여부, a/b size 변수 선언 및 입력
		int count = 0;
		int ten = 0;
		int a_size = a.length - 1;
		int b_size = b.length - 1;
		
		// 반복문 시작
		while(true) {
			// a, b, sum 선언
			int int_a;
			int int_b;
			int sum;
			
			// size보다 작으면 0, 크면 int_a 입력
			if(a_size - count < 0)
				int_a = 0;
			else
				int_a = Integer.parseInt(a[a_size - count]);

			// size보다 작으면 0, 크면 int_b 입력
			if(b_size - count < 0)
				int_b = 0;
			else
				int_b = Integer.parseInt(b[b_size - count]);
			 
			sum = int_a + int_b + ten; // 합계 계산
			
			// 10보다 크면 Ten++;, 작으면 Ten은 0
			if(sum >= 10) {
				sum = sum % 10;
				ten = 1;
			}
			else {
				ten = 0;
			}
			
			// StringBuilder 입력 및 Count++
			sb.append(sum);
			count++;
			
			// 마지막 값이 10을 넘는 경우 입력
			if(a_size - count < 0 && b_size - count < 0) {
				if(ten == 1)
					sb.append(ten);				
				break;
			}
		}
		
		System.out.print(sb.reverse()); // 뒤집어서 결과 출력
	}
}

 

---

 

세 번째 방법

위와 마찬가지로 풀지만 좀더 최적화를 시킨 코드입니다

이 코드를 참고해서 작성했습니다

https://www.acmicpc.net/source/26736065

int[]배열을 선언 int[]배열을 통해 하나씩 값을 더하여 결과를 출력합니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		// BufferedReader, StringTokenizer, StringBuilder 선언 및 입력 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		StringBuilder sb = new StringBuilder();

		// str_A, str_B 값 입력
		String str_A = st.nextToken();
		String str_B = st.nextToken();
		
		int max_length = Math.max(str_A.length(), str_B.length()); // Max값을 구한다
		
		// A, B 배열 선언
		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) - 48;			
		}

		// B의 배열 데이터 입력
		for(int i = str_B.length() - 1, idx = 0; i >= 0; i--, idx++) {
			B[idx] = str_B.charAt(i) - 48;
		}
		
		// 반복문을 사용 A + B를 계산
		for(int i = 0; i < max_length; i++)
		{
			int value = A[i] + B[i];
			A[i] = value % 10;
			A[i + 1] += (value / 10);
		}
		
		// 마지막값이 0이 아니면 1을 입력
		if(A[max_length] != 0)
		{
			sb.append(A[max_length]);
		}
		
		// 반복문을 사용 결과 입력
		for(int i = max_length - 1; i >= 0; i--)
		{
			sb.append(A[i]);
		}
		
		System.out.print(sb); // 결과 출력
	}
}

 

---

 

속도 비교

1. BigInteger 사용

2. String[] 배열 사용

3. int[] 배열 사용

세 가지 방법으로 풀었을 때의 시간과 메모리입니다

3번 방식이 압도적으로 빠른 것을 볼 수 있습니다

 

이상 백준 알고리즘 10757번 큰 수 A+B를 풀은 내용이었습니다

 

다음 문제 : 2021.05.27 - [알고리즘/알고리즘JAVA] - [백준알고리즘/기본 수학 1단계] 1011번 문제 : Fly me to the Alpha Centauri

이전 문제 : 2021.05.26 - [알고리즘/알고리즘JAVA] - [백준알고리즘/기본 수학 1단계] 2839번 문제 : 설탕 배달