[Baekjoon(JAVA) - Algorithm] 2609번: 최대공약수와 최소공배수 (유클리드 호제법)

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

2609번: 최대공약수와 최소공배수

 

---

문제를 풀기 앞서, 유클리드 호제법으로 구하는 방법은 그동안 알던 최대공약수, 최소공배수 방법과는 조금 다르다.

 

- 최대공약수

숫자 A, B가 있다면 두 수를 나누어서 나온 나머지가 R이라고 해보자.

이때 R이 0이면 B가 최대공약수가 된다.

만약 R이 0이 아니라면 A에 B를 대입하고, B에 R을 대입해서 두 수를 다시 나누는 방법을 R이 0일 될 때까지 반복한다.

 

100, 46을 예로 들어보자.

A	B	result (R)
100	46	100 % 46 = 8
46	8	46 % 8 = 6
8	6	8 % 6 = 2
6	2	6 % 2 = 0

A % B의 결과 R이 0일 때 B값인 2가 최대공약수가 된다.

 

A, B 숫자 중 앞의 숫자가 크면 좋겠지만 위 예시와 반대로 A는 46, B는 100일 때 46 % 100는 46이므로 두 번째부터 A는 100, B는 46이 되므로 위 표처럼 실행될 것이다.

 

- 최소공배수

위의 예시에서 최대공약수 2를 구했다.

최소공배수를 구하는 식은 A와 B를 곱하고 최대공약수를 나누는 것이다.

따라서 100 * 46 / 2 를 하여 2300이 나온다.

 

유클리드 호제법으로 최대공약수, 최소공배수를 알았으니 이제 문제를 풀어보자.

Answer

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

public class Main {
    public static void main(String[] args) {
        int num1 = 0;
        int num2 = 0;
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            num1 = Integer.parseInt(st.nextToken());
            num2 = Integer.parseInt(st.nextToken());
        } catch (IOException e) {
            System.err.println("ERROR = " + e.getMessage());
        }

        int gcd = gcd(num1, num2);
        int lcm = num1 * num2 / gcd;

        StringBuilder sb = new StringBuilder();
        sb.append(gcd);
        sb.append("\n");
        sb.append(lcm);
        System.out.print(sb);
    }

    static int gcd(int num1, int num2) {
        int remainedNum = 0;
        while (num1 % num2 != 0) {
            remainedNum = num1 % num2;
            num1 = num2;
            num2 = remainedNum;
        }
        return num2;
    }
}

 

Code Review

try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    num1 = Integer.parseInt(st.nextToken());
    num2 = Integer.parseInt(st.nextToken());
} catch (IOException e) {
    System.err.println("ERROR = " + e.getMessage());
}

`try-with-resources`로 try에 객체 자원을 받아서 try문이 종료되면 `br.close()`없이 자동으로 자원을 반환한다.

`System.in`으로 사용자로부터 입력받은 데이터를 바이트 스트림으로 받는다.

`InputStreamReader` 클래스로 바이트 스트림을 문자 기반 스트림으로 변환한다.

`BufferedReader` 클래스로 문자 스트림을 읽는다.

 

`StringTokenizer` 객체를 문자열 한 행 `br.readLine()`과 공백 구분자로 생성한다.

`st.nextToken()` 메서드로 공백으로 구분된 문자를 가져오고 `Integer.parseInt()`로 정수 변환하여 num 변수에 대입한다.

 

우선 최대공약수를 구해보자.

int gcd = gcd(num1, num2);

생성한 `gcd()` 메서드 인자로 num1과 num2를 넘겨서 최대공약수를 return 받자.

 

static int gcd(int num1, int num2) {
    int remainedNum = 0;
    while (num1 % num2 != 0) {
        remainedNum = num1 % num2;
        num1 = num2;
        num2 = remainedNum;
    }
    return num2;
}

num1을 num2로 나눴을 때의 나머지를 대입할 `remainedNum` 변수를 선언한다.

num1을 num2로 나눴을 때 0이 되기 전까지 계속 반복한다.

 

num1을 num2로 나눴을 때의 나머지 `remainedNum`을 구해놓고,

num1은 num2를, num2는 `remainedNum`을 대입한다.

이를 반복하다 보면 `remainedNum`이 0이 될 때가 있다. 그때의 num2가 우리가 구할 최대공약수이다.

 

최대공약수를 구했으니 이제 최소공배수를 구해보자.

int lcm = num1 * num2 / gcd;

최소공배수는 num1과 num2를 곱한 값에 최소공배수를 나눠주면 된다.

 

StringBuilder sb = new StringBuilder();
sb.append(gcd);
sb.append("\n");
sb.append(lcm);
System.out.print(sb);

출력을 한 줄씩 해야 돼서 `StringBuilder` 객체를 생성한 후 `append()` 메서드로 출력할 데이터들을 추가했다.

 

Result

이번 문제도 기존에 알고 있던 방법으로 풀려다 보니 성능이 너무 안 좋았다.

어느 정도 문제를 풀 때 필요한 사전지식은 알고 풀어야겠다..