백준 10757 JAVA풀이

문제

 

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

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

 

풀이

 

무턱대고 int, long으로 받아서 A+B를 하면 안된다 그 이유는 10^10000은 int와 long의 범위를 훨씬 넘기 때문이다.

그렇다면 일반적인 수의 '+' 연산을 사용할수 없다는 거고 우리가 직접 더하기 알고리즘을 구현해야 하는 것이다.

i) A, B를 String으로 입력받는다

ii) A, B를 알고리즘에 넣고 String으로 반환한다.

iii) String출력

 

Algorithm

i) 더하기는 예전부터 배웠듯이 일의 자리 수부터 더해야 한다.

ii) 두개를 더했는데 10을 넘어가면 앞에 1의 자리에 1을 올려준다.

iii) 같은 자릿수만큼 더했더라고  1999999+ 1 인경우 1의자리수만 처리해서는 안된다. 이런점을 주의해서 알고리즘을 짜야 할 것이다.

 

1) A와 B를 각각 int 배열에 할당해 줄 것이다 (charAt을 사용해서)

2) 각각 배열의 제일 끝에 자리부터(1의자리부터) 더하기를 시작할 것이다.

3) 더하기는 가장긴 자릿수 까지 계속 진행 될 것이다.

import java.util.*;
import java.io.*;
import java.lang.Integer;

public class Main{
    public static void func(String A,String B){

        String str=null;
        int max=Math.max(A.length(),B.length());
        int[] a =new int[max+1];
        int[] b =new int[max+1];
        //A 를 int 배열에 할당
        for(int i=0;i<max;i++){
            if(A.length()==max){
            a[max-i]=(int)(A.charAt(A.length()-1-i)-'0');
            }
            else{
                if(i<A.length()){
                    a[max-i]=(int)(A.charAt(A.length()-1-i)-'0');
                }
                else{
                    a[max-i]=0;
                }
            }
        }
        //B 를 int 배열에 할당
        for(int i=0;i<max;i++){
            if(B.length()==max){
                b[max-i]=(int)(B.charAt(B.length()-1-i)-'0');
            }
            else{
                if(i<B.length()){
                    b[max-i]=(int)(B.charAt(B.length()-1-i)-'0');
                }
                else{
                    b[max-i]=0;
                }
            }
        }
        int add=0; //자릿수를 더했는데 올림을 해야하면 1 아니면 0
        int tmp[]=new int[max+1]; //더한값을 저장
        for(int i=max;i>0;i--){
            tmp[i]=((a[i]+b[i]+add)%10); //각 자릿수 더한값을 %10
            if(a[i]+b[i]+add>=10){
                add=1; //더한값이 10을 넘으면 올림
            }
            else {
                add=0; //아니면 0
            }
        }
        if(add==1){ //마지막 제일 높은 자리에서 올림이 된 경우 tmp[0]에 1을 저장
            tmp[0]=1;
            for(int i=0;i<max+1;i++) {
                System.out.print(tmp[i]);
            }
        }
        else{ //아닌경우 tmp[1]부터 출력
            for(int i=1;i<max+1;i++) {
                System.out.print(tmp[i]);
            }
        }
    }
    // A와 B를 char array로 받고 길이가 더 긴 array를 기준으로 tmp char array를 생성한다
    // 1의자리 부터 두개를 더하여 나간다
    // 길이가 짧은 array의 index가 0이 되면
    public static void main(String args[])throws IOException {
          BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st=new StringTokenizer(br.readLine());
          String A=st.nextToken();
          String B=st.nextToken();
          func(A,B);
        }
    }

 

 

 

피드백

코드가 길어져서 어딘가 어렵게 푼 부분이 있는것 같아서 짧게 바꿔볼려고 노력중이다.

char 숫자를 int 숫자로 바꾸는 과정에서 그냥 (int) 1 ~(int) 2로 하는 것이 아니라 (int) ('1'-'0') 을 꼭 해야한다는 부분을 까먹어서 한동안 오류가 났다.