lango

찍먹? 부먹?
난 부먹 개발자.

3 minute read



입출력 예시

Input
9223372036854775807 9223372036854775808
Output
18446744073709551615


문제 풀이

이 문제에서 주어지는 입력값의 경우 최대 10의 10000승으로 일반적으로 큰 값에 활욛되는 long 타입의 범위를 초과한다.
문자열을 입력받아 직접 덧셈을 구현하는 방식과 BigInteger 클래스를 활용하는 방식 두가지로 풀어보았다.


BigInteger 활용

보통 정수는 int를 많이 사용하고, int의 표현 범위를 넘어서면 long형을 사용해야 한다.

- int long
저장공간 4byte 8byte
범위 -2147483648 ~ 2147483647 -9223372036854775808 ~ 9223372036854775807


문제에선 10의 10000승으로 long형의 범위를 아득히 뛰어넘기 때문에 문자열로 취급하는 BigInteger 클래스를 사용할 수 있다.

BigInteger란?
long형을 뛰어넘는 더 큰 범위의 정수를 다룰 때 사용하는 클래스로 java.math 패키지에 속한다. 사칙연산을 활용할 때 기호로 할 수 없고 BigInteger에서 제공하는 메서드를 이용해야 한다.
클래스 객체로 선언하여 파라미터로 문자열을 넘겨주고, add 메서드로 덧셈을 할 수 있다.

BigInteger 클래스를 활용한 코드를 작성해보자.

1
2
3
4
5

StringTokenizer st = new StringTokenizer(br.readLine());
BigInteger A = new BigInteger(st.nextToken());
BigInteger B = new BigInteger(st.nextToken());

bw.write(A.add(B)+"\n");

코드는 간단하다. BigInteger A와 B를 입력 문자열대로 만들어서 add()메서드로 A+B 덧셈연산을 하였다.



직접 덧셈 구현

BigInteger 클래스를 활용하여 간단하게 풀 수도 있지만, 직접 덧셈을 구현해보는 것도 재밌겠다 싶어 직접 덧셈을 구현해보았다.
덧셈을 구현하기 위해 정한 아이디어는 다음과 같다.

  • 입력받은 A와 B를 가장 낮은 자리수부터 덧셈을 해야하기 때문에 역순으로 배열에 저장하여 서로를 덧셈한다.
  • 두 수를 덧셈했을 때, 더 큰 자리수를 가진 수의 길이를 덧셈 결과 배열의 길이로 해야 한다.
  • 두 수를 덧셈하여 10이 넘어가면, 현재 자리는 10으로 나눈 나머지가 값이 되고, 다음 자리값에 +1을 해준다.


위 아이디어대로 코드를 작성해보자.

1
2
3

StringTokenizer st = new StringTokenizer(br.readLine());
String str_A = st.nextToken();
String str_B = st.nextToken();

먼저 두 수 A와 B를 입력받자.

1

int big_len = Math.max(str_A.length(), str_B.length());

그리고 실제 두 수의 덧셈을 진행할때 더 큰 자리수만큼 덧셈연산을 해야 하기에 더 큰 자리수의 길이를 저장해둔다.

1
2
3
4
5
6
7
8
9
10

int[] A = new int[big_len+1];
int[] B = new int[big_len+1];

for(int i=0; i<str_A.length(); i++) {
    A[i] = str_A.charAt(str_A.length()-i-1)-'0';
}

for(int i=0; i<str_B.length(); i++) {
    B[i] = str_B.charAt(str_B.length()-i-1)-'0';
}

이제 문자열 A와 B를 역순으로 각 배열에 저장한다.
저장할 때 ‘0’을 빼준 이유는 charAt()을 통해 char형으로 변환되어 있기에 ‘0’인 48씩을 빼주어야 실제 값을 저장할 수 있기 때문이다.

1
2
3
4
5

for(int i=0; i<big_len; i++) {
    int sum = A[i]+B[i];
    A[i] = sum%10;
    A[i+1] += (sum/10);
}

A배열과 B배열에 가장 낮은 자리순으로 저장했으니, A,B 중 큰 수 길이만큼 반복하며 덧셈 연산을 진행하면 된다.
유의할 점은 덧셈 결과를 A배열에 씌워야 덧셈 연산을 올바로 진행할 수 있다.
A의 현재 자리값은 두수의 합을 10으로 나눈 나머지값이 되고, 다음 자리값은 A 현재 자리에 두수의 합을 10으로 나눈 몫을 더해주면 된다.

1
2
3
4
5
6
7

StringBuilder sb = new StringBuilder();
if(A[A.length-1]!=0) sb.append(A[A.length-1]);

for(int i=A.length-2; i>=0; i--) {
    sb.append(A[i]);
}
bw.write(sb+"\n");

또한 낮은 자리수부터 역순으로 큰 자리수의 길이만큼 덧셈연산을 하기에 제일 앞 수 즉, 가장 높은 자리수가 0일 수도 있다. 가장 높은 자리수는 0이 아닐때만 출력하면 된다.
역순으로 가장 낮은 자리수부터 덧셈 연산을 하여 거꾸로 A배열에 씌워졌으니, A배열을 거꾸로 출력하면 A와 B의 덧셈 연산 결과가 된다.



실행 결과

BigInteger보다 직접 덧셈을 구현한 방식이 더 빠른 것을 확인할 수 있었다.

BigInteger 활용 소요시간


BigInteger 클래스는 코드는 간단하지만 문자열 검사 같은 처리해야 하는 과정이 있기에 더 느렸던 것으로 보인다.

직접 덧셈 구현 소요시간




작성코드

BigInteger 활용 작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        BigInteger A = new BigInteger(st.nextToken());
        BigInteger B = new BigInteger(st.nextToken());

        bw.write(A.add(B)+"\n");

        bw.flush();
        bw.close();
        br.close();
    }
}

덧셈 구현 작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        
        String str_A = st.nextToken();
        String str_B = st.nextToken();

        int big_len = Math.max(str_A.length(), str_B.length());

        int[] A = new int[big_len+1];
        int[] B = new int[big_len+1];

        for(int i=0; i<str_A.length(); i++) {
            A[i] = str_A.charAt(str_A.length()-i-1)-'0';
        }

        for(int i=0; i<str_B.length(); i++) {
            B[i] = str_B.charAt(str_B.length()-i-1)-'0';
        }

        for(int i=0; i<big_len; i++) {
            int sum = A[i]+B[i];
            A[i] = sum%10;
            A[i+1] += (sum/10);
        }
        
        StringBuilder sb = new StringBuilder();
        if(A[A.length-1]!=0) sb.append(A[A.length-1]);
        
        for(int i=A.length-2; i>=0; i--) {
            sb.append(A[i]);
        }
        bw.write(sb+"\n");

        bw.flush();
        bw.close();
        br.close();
    }

}

회고

  • BigInteger 클래스에 대해서 공부할 수 있었고, 해당 클래스로 간단하게 풀 수 있는 문제지만, 직접 덧셈을 구현하는 코드를 작성하며, 덧셈을 어떻게 구현할 수 있을까? 재미있게 고민했던 것 같다.

You may also enjoy