백준 1934 최소공배수 With StringBuilder of Java

---

 

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

1934번: 최소공배수

 

---

 

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        
        Scanner in = new Scanner(System.in);
        
        int N = in.nextInt();
        
        StringBuilder sb = new StringBuilder();
 
        
        for(int i = 0; i < N; i++) {
            
            int a = in.nextInt();
            int b = in.nextInt();
            
            int d = gcd(a, b);    // 최소 공배수 구하기
            
            sb.append(a * b / d).append('\n');
        }
        System.out.println(sb);
        
    }
    
    
    // 최대공약수 반복문 방식
    public static int gcd(int a, int b) {
 
        while (b != 0) {
            int r = a % b; // 나머지를 구해준다.
 
            // GCD(a, b) = GCD(b, r)이므로 변환한다.
            a = b;
            b = r;
        }
        return a;
    }
} 

 

---

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        
        Scanner in = new Scanner(System.in);
        
        int N = in.nextInt();
        
        StringBuilder sb = new StringBuilder();
 
        
        for(int i = 0; i < N; i++) {
            
            int a = in.nextInt();
            int b = in.nextInt();
            
            int d = gcd(a, b);    // 최소 공배수 구하기
            
            sb.append(a * b / d).append('\n');
        }
        System.out.println(sb);
        
    }
    
    
    // 최대공약수 반복문 방식
    public static int gcd(int a, int b) {
 
        while (b != 0) {
            int r = a % b; // 나머지를 구해준다.
 
            // GCD(a, b) = GCD(b, r)이므로 변환한다.
            a = b;
            b = r;
        }
        return a;
    }
} 

---

이 문제도 유클리드 호제법을 사용해서 풀어준다. 먼저 스캐너를 통해서 테스트 케이스의 갯수를 N 변수에 받아준다. 그리고 StringBuilder 객체를 하나 만들어준다. 일반 스트링은 불변하기 때문에 계속 바뀔 때마다 새로운 문자열이 추가가 되어 메모리적으로 큰 공간을 차지하게 되는 반면에 StringBuilder는 계속 추가(변경)가 되는 형식으로 메모리를 비교적 덜 사용하게 된다. 그렇기에 이 객체를 하나 만들어주고 테스트 케이스의 갯수만큼 반복해 최소 공배수를 구할 숫자 두개를 입력 받는다. 그리고 최소 공배수를 구한 다음에 sb에 추가하고 그것을 for문을 빠져나와서 출력하면 된다. gcd (최대 공약수)를 찾는 과정은 예를 들어 설명하겠다. a가 48, b가 18이라고 가정해보자. r = a % b에서  48 % 18의 값, 즉 12를 r에 저장하게 된다. 그리고  a = b에서 a의 값이 18로 대체가 되고 b의 값이 12로 대체가 된다. 그런 다음 다시 r =  a % b에서 r = 18 % 12 -> r =6이되고 a = b를 통해 a = 12,  b = 6이 된다. 이 과정을 반복하면 a는 6이 되는데 즉 최대공약수는 6이다. 이렇게 최대 공약수를 a와 b를 곱해서 최대 공약수의 값으로 나누어주면 최소 공배수를 구할 수 있다.