백준 1934번 자바

1. 문제

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

 

2. 유클리드 호제법?

역시 자세한 설명은 네이버가 잘해준다.

https://terms.naver.com/entry.naver?docId=2073670&cid=47324&categoryId=47324 

유클리드 호제법

내가 할 일은 역시 코드로 구현하는 것이다.

 

먼저 해당 개념을 알고 처음 코드로 구현 한 것이다. 두 값 A,B를 받는다. 단 A >B이다.

mod연산(나머지연산)의 값이 0이 될 때까지 반복문을 돌린다.

이때 값을 swap해주면서 최종적으로 나온 B(최대공약수)를 반환한다.

public static int modSwap(int A, int B) {
		int mod = A%B;
		int temp = 0;

		while (mod != 0) {
			temp = mod;
			mod = B%temp;
			B = temp;
		}
		return B;
	}

 

하지만 다른분들의 코드를 보니 내 방식이 썩 좋지 않단 생각이 들었다.

대부분으로 재귀를 이용해서 유클리드 호제법을 구현한다.

또 해당 코드를 분석하면서 깨달은 것이 mod연산이 대소관계 구분을 하지 않기 때문에 a,b의 대소관계가 상관이 없다는 것이다.

public static int gcd(int a, int b) {
    if (b == 0)
      return a;
    else
      return gcd(b, a % b);
  }

 

3. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main1934 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		int[][] numbers = new int[T][2];

		StringTokenizer st;
		for (int i=0; i<T; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			if (A >= B) {
				numbers[i][0] = A;
				numbers[i][1] = B;
				continue;
			}
			numbers[i][0] = B;
			numbers[i][1] = A;
		}

		for (int i=0; i<T; i++) {
			int gcd = modSwap(numbers[i][0], numbers[i][1]);
			System.out.println((numbers[i][0]/gcd)*(numbers[i][1]/gcd)*gcd);
		}
	}
	
	public static int modSwap(int A, int B) {
		int mod = A%B;
		int temp = 0;

		while (mod != 0) {
			temp = mod;
			mod = B%temp;
			B = temp;
		}
		return B;
	}
}

 

4. 정리

구현이 어렵지 않아 쉽게 풀었지만 다른 정답을 보고 역시 아직 멀었구나라는 생각이 들었다. 충분히 생각해 볼 수 있는 부분임에도 놓친 것이 아쉽다. 다른 정답 코드를 아래에 첨부해 되새기자.

import java.util.*;
public class Main {
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    for (int i = 0; i < t; i++) {
      int a = sc.nextInt();
      int b = sc.nextInt();
      int result = a * b / gcd(a, b);
      System.out.println(result);
    }
  }
  public static int gcd(int a, int b) {
    if (b == 0)
      return a;
    else
      return gcd(b, a % b);
  }
}