[SW expert Academy] SWEA 16800번 구구단 걷기 자바(Java)

[D3] 구구단 걷기 - 16800

문제 링크

성능 요약

메모리: 24,292 KB, 시간: 497 ms, 코드길이: 931 Bytes

제출 일자

2023-10-20 23:39

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

SW Expert Academy

 

해결 방법

1. 만약 입력한 N 값이 소수라면 무조건 1 x N이다. 

2. N : i * j 일 때 i와 j의 차이가 최소일 때 (1,1)에서 가깝기 때문에 Math.sqrt(N) 값까지 확인해준다.

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

class Solution
{
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for(int tc = 1; tc <= T; tc++)
		{
            long N = sc.nextLong();
            long a = 0;
            long b = 0;
            
            if(isPrime(N)){
                a = 1;
                b = N;
            }else{
                    for(int i = 1; i <= Math.sqrt(N); i++){
                        if(N % i == 0){
                            a = i;
                            b = N / i;
                        }
                    }
            }        
            System.out.println("#" + tc +" " + (a+b-2));
        }
    }
    
    private static boolean isPrime(long N){
        for(int i = 2; i <= Math.sqrt(N); i++){
            if(N % i == 0){
                return false;
            }
        }
        return true;
    }
}

1. for문을 1부터가 아닌 sqrt(N)부터 시작해줌으로 속도를 단축 시킴

2. 변수에 값을 넣는게 아닌 바로 계산을 해줘서 가독성을 향상

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

class Solution
{
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for(int tc = 1; tc <= T; tc++)
		{
            long N = sc.nextLong();
            long result = 0;
            
            if(isPrime(N)){
                result = N - 1;
            }else{
                    for(int i = (int)Math.sqrt(N); i >= 1; i--){
                        if(N % i == 0){
                            result = (i + N / i) -2;
                            break;
                        }
                    }
            }        
            System.out.println("#" + tc + " " + result);
        }
    }
    
    private static boolean isPrime(long N){
        for(int i = 2; i <= Math.sqrt(N); i++){
            if(N % i == 0){
                return false;
            }
        }
        return true;
    }
}