백준 2839 설탕 배달 Java 풀이

문제

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

입력

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

출력

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

풀이

기본 수학이라는 카테고리에 고작 더하기라니...? 라는 황당한 생각이었지만 예제 입력을 보니 그 단위가 기본형 타입을 아득히 넘어서는 수치였다. 이는 단순히 long a + long b 로는 구할 수 없었고 초등학교 시간에 배운 덧셈 방식의 알고리즘을 구현하면 될 것 같았다.

  9223372036854775807
+ 9223372036854775808
---------------------
	               15
                 161

대충 이런 느낌? 단위별로 쪼개어 계산하며 자릿수를 하나하나 더하여 배열로 처리하면 간단하다. 그런데 굳이 이런 알고리즘을 구현해야할까...? 자바에서 편리한 라이브러리를 제공하고 있는데... 이러한 알고리즘 구현은 매우 복잡하고 비효율적이다.

풀이 코드

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 br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		br.close();
		
		BigInteger bigA = new BigInteger(st.nextToken());
		BigInteger bigB = new BigInteger(st.nextToken());
		bigA = bigA.add(bigB);

		System.out.println(bigA.toString());
	}

}

그래도 아쉬우니... 위에서 생각한 알고리즘을 직접 구현해보았다.

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 br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		br.close();

		String num1 = st.nextToken();
		String num2 = st.nextToken();

		int maxLength; // 두 숫자 중 가장 큰 수의 자릿수

		if (num1.length() >= num2.length()) {
			maxLength = num1.length();
		} else {
			maxLength = num2.length();
		}

		// 덧셈 중 자릿수가 커질 수 있으므로 배열 크기를 1만큼 더 크게함
		int numA[] = new int[maxLength + 1];
		int numB[] = new int[maxLength + 1];

		// 배열 초기화 - 알고리즘 구현 편의를 위해 1의 자릿수를 앞에서 부터 채움 (역순)
		for (int digit = num1.length() - 1, index = 0; digit > -1; digit--, index++) {
			numA[index] = num1.charAt(digit) - '0'; // char 타입이므로 '0'을 뺀다.
		}
		for (int digit = num2.length() - 1, index = 0; digit > -1; digit--, index++) {
			numB[index] = num2.charAt(digit) - '0'; // char 타입이므로 '0'을 뺀다.
		}

		// 두 배열을 더함 - 새 배열에 담지 않고 기존 배열을 사용함
		for (int i = 0; i < maxLength; i++) {
			int result = numA[i] + numB[i];
			numA[i] = result % 10; // 10으로 나눈 나머지가 자릿수
			numA[i + 1] += result / 10; // 10으로 나눈 몫이 있으면 올려줌
		}

		// 배열 출력
		StringBuilder result = new StringBuilder();
		if (numA[maxLength] != 0) {
			result.append(numA[maxLength]); // 자릿수가 커졌다면 포함
		}

		for (int i = maxLength - 1; i > -1; i--) { // 역순으로 계산하였으니 출력도 역순
			result.append(numA[i]);
		}

		System.out.println(result);

	}

}

생각했던대로 많이 번거롭고 불편하지만... 어째서인지 성능은 더 좋다..!?