[백준 1009 : JAVA] 분산처리

개요

 

a^b 의 경우 a가 어떤 숫자여도 1의 자릿수만 신경 쓰면 된다!!

a의 1의 자릿수는 0, 1, 2 .... 8, 9 까지만 존재한다!!

 

문제 

 

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

 

입력

 

풀이

 

개요에서 말한 것과 같이 a의 1의 자릿수가 0 ~ 9 인 경우에 어떤 반복이 발생하는지 확인하면 된다.

 

a = 1 인 경우 --> 1 , 1 , 1 ...  (1 반복)

a = 2 인 경우 --> 2 , 4 , 8 , 6 ...  (2, 4, 8, 6 반복)

a = 3 인 경우 --> 3 , 9 , 7 , 1 , 3 ...  (3, 9, 7, 1 반복)

a = 4 인 경우 --> 4 , 6 , 4 ...  (4, 6 반복)

a = 5 인 경우 --> 5 , 5 , 5 ...  (5 반복)

 

 

1. 반복되는 숫자를 list에 저장

2. b / list.size() --> 이 값을 통해 list의 몇번째 값인지 확인

3. b / list.size()가 0인 경우 10번째 컴퓨터로 분산 처리한 것이므로 10으로 변경 (문제에 주어짐)

 

코드

import java.io.*;
import java.util.*;

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException{
        // testCase 갯수 입력
        int testCnt = Integer.parseInt(br.readLine());

        for(int i = 0 ; i < testCnt; i++){
            // a, b 값 입력
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // 풀이 메소드 호출
            int answer = solve(a, b);

            // 출력 버퍼 write
            bw.write(answer + "\n");
        }

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

    public static int solve(int a, int b){
        int result = 0;

        // 입력받은 a의 1의 자릿수
        int calcA = a % 10;
        // calcA * calcA * ... 을 저장할 변수
        // 초기에는 calcA로 셋팅
        int value = calcA;

        // a^b가 이루어질 때 1의 자릿수를 저장할 리스트
        // ex) a = 3인 경우 list = {3, 9, 7, 1}
        ArrayList<Integer> list = new ArrayList<>();
        // list에 중복된 값이 들어가지 않도록 체크할 배열
        boolean[] isCheck = new boolean[10];

        list.add(value);
        isCheck[value] = true;

        while(true){
            // calcA를 곱해서 1의 자릿수만 확인
            value = (value * calcA) % 10;
            
            // value가 이미 list에 들어있는 값이라면
            // 앞으로 순환된 값이 들어오므로 break
            if(isCheck[value] == true) break;

            list.add(value);
            isCheck[value] = true;
        }

        // (b - 1)을 해야 list의 index와 같아짐
        int calcB = (b - 1) % list.size();
        // 0이면 10번째 컴퓨터임
        result = list.get(calcB) != 0 ? list.get(calcB) : 10;

        return result;
    }   
}