1009 자바 ] 분산처리(풀이)

※ 문제

출처 : (https://www.acmicpc.net/problem/1009)

---

1) 실패코드

나는 2번의 삽질 끝에 성공하였다.

첫 번째는 BigInteger를 활용해서 풀었는데 메모리 초과가 발생하였다. 이때까지만 해도 왜 메모리를 많이 잡는 지 이해하지 못하였다.

 

① Biginteger로 작성한 코드

import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<BigInteger> list = new ArrayList<>();
    static BigInteger num = new BigInteger("10");
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);

        int count = scan.nextInt();
        String inputData = scan.nextLine();

        for(int i=0; i<count; i++) {
            inputData = scan.nextLine();
            String[] arr = inputData.split(" ");

            BigInteger a = BigInteger.valueOf(Long.parseLong(arr[0]));
            int b = Integer.parseInt(arr[1]);

            System.out.println(a.pow(b).remainder(num));
        }

    }
}

 

두 번째 방법은 10대의 컴퓨터만 존재하기 때문에 1의 자릿 수만 필요하다는 것을 깨달았다. 그리고 작성한 코드이다.

하지만 메모리 초과가 발생하였다. 삽질을 엄청한 결과 String.valueof()에서 128MB를 초과하는 메모리를 사용했다.

 

② 1의 자릿수 방식으로 작성한 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int count = scan.nextInt();
        String inputData = scan.nextLine();

        for(int i=0; i<count; i++) {
            inputData = scan.nextLine();
            String[] arr = inputData.split(" ");

            int a = Integer.parseInt(arr[0]);
            int b = Integer.parseInt(arr[1]);

            int result = a;

            for(int j=0; j<b-1; j++) {
                result *= a;
                for(int k=0; k<String.valueOf(result).length(); k++) {
                    result %= 10;
                }
            }

            if(String.valueOf(result).substring(String.valueOf(result).length()-1).equals("0")) result = 10;
            System.out.println(result);
        }
    }
}

---

 

2) 성공코드

위 실패 사례로 숫자 범위를 초과하는 큰 수를 계산하는 경우 메모리를 효율적으로 사용하기 위해서는 형 변환을 하지 않고 계산하는 것이 효율적이라는 것을 알았다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int count = scan.nextInt();
        String inputData = scan.nextLine();

        for(int i=0; i<count; i++) {
            inputData = scan.nextLine();
            String[] arr = inputData.split(" ");

            int a = Integer.parseInt(arr[0]);
            int b = Integer.parseInt(arr[1]);

            int result = a;

            // 주어진 a의 1의 자릿 수 구하기
            for(int k=0; k < (int) (Math.log10(result)+1); k++) {
                result %= 10;
            }

            // 거듭제곱 후 1의 자릿 수 구하기
            for(int j=1; j<b; j++) {
                result *= a;
                result %= 10;
            }
            
            if(result == 0) result = 10;
            System.out.println(result);
        }
    }
}