[JAVA + Python] BOJ 1934 최소공배수

출처 : 백준

 

간단하게 최소공배수를 구하는 문제이다. 이 문제는 자바랑 파이썬으로 동시에 풀어봤는데 그 실행시간의 차이가 커서 기록해두고자 한다.

 

우선 같은 알고리즘을 사용했다. 두 수 A와 B가 주어졌을 때 작은 값을 Min, 큰 값을 Max로 저장하고 반복문을 1부터 Min까지 하나씩 증가하면서(i라 하겠다) (Max*i)% Min==0 인 i값을 찾으면 break로 탈출하는 것이다. 

 

파이썬으로 먼저 보면 다음과 같다.

T = int(input())
for i in range (T):
    A, B = map(int, input().split())
    Min = min(A,B)
    Max = max(A,B)
    for i in range(1,Min+1):
        if (Max*i)%Min==0:
            print(Max*i)
            break

 

코드의 길이는 짧지만, 

이를 제출하니 시간 초과가 나왔다. 살짝 꼼수이긴 한데 이럴 때는 Pypy3 로 제출하면 어느 정도는 시간을 줄여서 통과할 수 있다.

 

이제 같은 알고리즘인데 자바로 구현해보았다. Input과 Output은 실행속도가 빠르다는 BufferedReader와 BufferedWriter를 사용하였다.

 

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        
        for(int i=0; i<N;i++) {
        	st = new StringTokenizer(br.readLine());
        	int A = Integer.parseInt(st.nextToken());
        	int B = Integer.parseInt(st.nextToken());
        	int Min = Math.min(A, B);
        	int Max = Math.max(A, B);
        	
        	for(int j=1;j<=Min;j++) {
        		if((Max*j)%Min==0){
        			bw.write(Max*j + "\n");
        			break;
        		}
        	}
        }
        bw.flush();
        bw.close();
    }
}

 

이제 시간 차이와 메모리 차이를 보면 자바가 훨씬 우위에 있는 것을 알 수 있다. 

이러한 차이는 자바가 컴파일 언어이고 파이썬은 인터프리터 언어이기 때문이다. 컴파일 언어는 개발자가 입력한 코드를 바로바로 해석해 기계어로 변환하는 (바이트 코드를 미리 배포하는) 언어이기 때문에 예습을 해놓는다고 볼 수 있다. 반면 인터프리터는 코드를 실행시켰을 때 그제야 한 줄 한 줄 읽어나가며 기계어로 변환하기 때문에 당연히 속도 측면에서 차이가 날 수밖에 없다. 하지만 무조건 자바가 빠르다고 볼 수도 없는 게 어떤 문제에서는 파이썬이 훨씬 빠르게 실행되는 것도 볼 수 있기 때문이다.