글 읽기 - 수행시간이 너무 깁니다 ㅠ

alsgur077 5년 전 0

문제는 맞았는데 수행시간이 1초를 넘어가네요ㅠ 나름 시간을 줄여보려고하는데 줄어들지 않네요.

혹시 저의 코드중 어느부분이 가장 비효율적으로 작동하는건지 알수있을까요 ㅠ?

package problem_1963;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int testCase = toInteger(br.readLine());
		ArrayList<Integer> primeList = new ArrayList<>();
		Erastos(primeList);
		for(int i=0 ; i<testCase ; i++) {
			String[] input = br.readLine().split(" ");			
			int before = toInteger(input[0]);
			int after  = toInteger(input[1]);
			if(before == after)
				System.out.println(0);
			else
				BFS(primeList, before, after);			
		}
	}
	
	public static ArrayList<Integer> Erastos(ArrayList<Integer> primeList) {		 
		int sqrt = (int)Math.sqrt(9999);
		int notPrime=0;
		for(int i=1000 ; i<10000 ; i++) {
			for(int j=2 ; j<=sqrt ; j++) {
				if(i%j==0) {
					notPrime = 1;
					break;
				}										
			}
			if(notPrime==0)
				primeList.add(i);
			notPrime=0;
		}
		return primeList;
	}
	
	public static void BFS(ArrayList<Integer> primeList, int before, int after) {
		int[] transform = new int[10000];
		Arrays.fill(transform, 10000);
		Queue<Integer> q = new LinkedList<>();
		q.add(before);
		transform[before] = 0;
		
		while(!q.isEmpty()) {
			int num = q.poll();
			for(int i=0 ; i<primeList.size() ; i++) {
				int prime = primeList.get(i);
										
				if(transform[prime] != 10000)
					continue;					
				
				if(checkDigit(num, prime)) {
					if(prime==after) {
						System.out.println(transform[num] + 1);
						return;
					}						
					q.add(prime);
					transform[prime] = transform[num] + 1;
				}				
			}
		}
		System.out.println("Impossible");
		return; 
	}
	
	public static boolean checkDigit(int num1, int num2) {
		int equal = 0;
		for(int i=0 ; i<4 ; i++) {
			if(num1/(int)Math.pow(10, 3-i) == num2/(int)Math.pow(10, 3-i)) {
				num1 = num1 % (int)Math.pow(10, 3-i);
				num2 = num2 % (int)Math.pow(10, 3-i);
				equal++;
			}
			else {
				num1 = num1 % (int)Math.pow(10, 3-i);
				num2 = num2 % (int)Math.pow(10, 3-i);
			}
		}
		if(equal==3)
			return true;
		else
			return false;
	}
	
	public static int toInteger(String string) {
		return Integer.parseInt(string);
	}
}

tmdfur11 3년 전 0

자바에서는 어떤지 모르겠지만 pow() 함수가 double형 연산이라 비용이 많이 드는 연산이라고 알고있습니다. pow()를 쓰지 않고 다른 방법을 생각해보시는게 어떨까요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

수행시간이 너무 깁니다 ㅠ

alsgur077 5년 전 0

tmdfur11 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말