[Java] 1단계. 최소공배수 [1934번]

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

• 예제 입력1

3
1 45000
6 10
13 17

• 예제 출력1

45000
30
221

---

1. 문제 접근
   • 입력
     
     • 첫째 줄 : 테스트 케이스의 개수 T(1 <= T <= 1,000)
     • ~ T번째 줄 : A와 B
   • 출력
     • T개의 줄에 A와 B의 최소공배수를 한 줄에 하나씩 출력

• 문제 해결
  • 최소공배수를 구하는 방법 → A * B / 최대공약수
  • 최대공약수를 구하는 방법 (유클리드 호제법)
    
    • 두 수 a와 b가 있을 때, a를 b로 나눈 나머지를 구함 (r = a mod b)
    • a와 b를 b와 r로 바꾸고 1번을 반복
    • 나머지가 0이 되었을 때 b값이 최대공약수
  • ex) a = 6,  b = 15
    1. 6 mod 15 = 6 → a = 15, b =6
    2. 15 mod 6 = 3 → a = 6, b = 3
    3. 6 mod 3 = 0 → 나머지가 0이므로 마지막 b(3)이 최대 공약수
    4. a(6) * b(15) / 최대공약수(3) = 30
    5. 따라서, 6과 15의 최소공배수 30 
• 내 풀이 [메모리 : 15,256 KB / 시간 : 120 ms]

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

    for(int i = 0; i < T; i++){
        String[] input = br.readLine().split(" ");
        int a = Integer.parseInt(input[0]);
        int b = Integer.parseInt(input[1]);
        int r;
        int tmpA = a;
        int tmpB = b;
        while(true){
            r = tmpA % tmpB;
            if(r == 0) break;
            tmpA = tmpB;
            tmpB = r;
        }
        sb.append(a * b / tmpB).append("\n");
    }

    System.out.println(sb);
}

• ChatGPT 풀이 [메모리 : 14,620 KB / 시간 : 120 ms]

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

public static int lcm(int a, int b) {
    return a * (b / gcd(a, b));
}

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

    for (int i = 0; i < T; i++) {
        String[] input = br.readLine().split(" ");
        int a = Integer.parseInt(input[0]);
        int b = Integer.parseInt(input[1]);

        sb.append(lcm(a, b)).append("\n");
    }

    // 모든 결과를 한 번에 출력
    System.out.println(sb);
}

---

• 나의 풀이는 약간 하드코딩한 듯한 느낌이였는데, 유클리드 호제법을 하는 부분을 재귀 호출로 푸는 방법을 보고 아직 많이 부족하다고 느낌
• 특정 조건이 발생하기 전까지 반복되는 while문 같은 경우 재귀 호출로 구현하는 것을 계속 생각해볼 것