[백준] 적어도 대부분의 배수 - 1145번

느낀점

• 코드 개선의 중요성:
  • 코드 개선을 통해 가독성과 효율성을 높일 수 있어 좋았습니다. 시간 복잡도를 유지하면서도 코드의 구조를 개선하여 더 나은 성능과 유지보수성을 확보할 수 있음을 느꼇습니다..
• 스트림 API의 강력함:
  • Java 스트림 API를 활용하여 복잡한 계산을 간결하고 직관적으로 표현할 수 있음을 다시 한 번 느꼈습니다. 스트림 API는 코드의 가독성을 크게 향상시킬 수 있는 강력한 도구입니다.
• 모듈화와 함수 분리의 중요성:
  • 함수 분리와 모듈화를 통해 코드의 재사용성과 유지보수성을 높일 수 있음을 확인했습니다. 각 함수가 하나의 역할을 담당하도록 함으로써 코드의 복잡성을 줄이고, 필요한 경우 쉽게 수정할 수 있었습니다.
• 효율적인 메모리 사용:
  • 메모리 사용 최적화를 통해 코드의 성능을 개선할 수 있음을 배웠습니다. 불필요한 데이터 구조를 제거하고, 필요한 연산만을 수행하도록 함으로써 메모리 사용을 최소화할 수 있었습니다.

적어도 대부분의 배수

2 초	128 MB	13302	8298	7095	63.252%

문제

다섯 개의 자연수가 있다. 이 수의 적어도 대부분의 배수는 위의 수 중 적어도 세 개로 나누어 지는 가장 작은 자연수이다.

서로 다른 다섯 개의 자연수가 주어질 때, 적어도 대부분의 배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다.

출력

첫째 줄에 적어도 대부분의 배수를 출력한다.

예제 입력 1

30 42 70 35 90

예제 출력 1

210

예제 입력 2

1 2 3 4 5

예제 출력 2

4

예제 입력 3

30 45 23 26 56

예제 출력 3

1170

예제 입력 4

3 14 15 92 65

예제 출력 4

195

1차 코드

결과: 통과

2차 리팩토링 코드

결과: 통과

package 적어도대부분의배수;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;

/**
     [시간 복잡도] -> O(N^3)

    [개선점]
    1. 코드 간결화 및 가독성 향상
        - Arrays.stream(combinations).mapToInt(comb -> lcm(comb[0], comb[1], comb[2])).min().orElseThrow();와 같이
          스트림을 활용하여 조합 생성과 최소 공배수 계산을 하나의 파이프라인으로 처리했습니다.

     2. 메모리 사용 최적화
        - 이전 코드에서는 조합 배열(lcmArr)과 최소 공배수 배열(answerArr)을 따로 생성하고 저장하는 방식을 사용했지만,
          리팩토링 된 코드2에서는 조합 배열만을 사용하여 스트림 내에서 직접 최소 공배수를 계산하고 최소값을 찾습니다.
           즉, 불필요한 배열 할당을 줄여 메모리 사용을 최적화했습니다.

     3. 함수 분리 및 재사용성
        -  조합 크기 계산 함수(combinationSize), 조합 생성 함수(generateCombinations), 최소 공배수 계산 함수(lcm) 등을
           별도로 정의하여 가독성과 유지보수성을 높였습니다.

     4. 팩토리얼 계산의 명확성
        - 팩토리얼 계산이 필요한 조합 크기 계산(combinationSize)에서 이를 활용하여 코드의 일관성을 유지했습니다.

     5. 시간 복잡도 유지
         - 최종적으로 시간 복잡도는 이전 코드 시간 복잡도 O(N^3)와 동일하지만
         스트림 API를 활용하여 코드가 간결해지고 유지보수성이 높아졌습니다.

    [결론] 
        - 알고리즘의 본질적인 시간 복잡도는 유지하면서 코드의 효율성과 가독성을 개선했습니다.

 */
public class Main2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        BufferedReader br = new BufferedReader(new StringReader(input1()));

        // 버퍼로부터 첫줄을 읽어 Arrays.stream을 이용하여 정수 배열로 변환
        int[] intArr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int lcmSize = combinationSize(intArr.length, 3);
        int[][] combinations = generateCombinations(intArr, lcmSize, 3);

        int answer = Arrays.stream(combinations)
                .mapToInt(comb -> lcm(comb[0], comb[1], comb[2]))
                .min()
                .orElseThrow();

        System.out.println(answer);
    }

    // --------------------------------------------------------
    // 두 수의 최대공약수를 구하는 메소드
    static int gcd(int numA, int numB){
        while(numB != 0){
            int temp = numB;
            numB = numA % numB;
            numA = temp;
        }
        return numA;
    }

    // 두 수의 최소공배수를 구하는 메소드
    static int lcm(int numA, int numB){
        return (numA * numB) / gcd(numA, numB);
    }

    static int lcm(int numA, int numB, int numC){
        return lcm(lcm(numA, numB), numC);
    }

    // 조합의 크기를 구하는 메소드
    static int combinationSize(int n, int r) {
        return factorial(n) / (factorial(n - r) * factorial(r));
    }

    // 조합을 생성하는 메소드
    static int[][] generateCombinations(int[] arr, int size, int r) {
        int[][] combinations = new int[size][r];
        int idx = 0;

        for(int i = 0; i < arr.length - 2; i++){
            for(int j = i + 1; j < arr.length - 1; j++){
                for(int k = j + 1; k < arr.length; k++){
                    combinations[idx++] = new int[]{arr[i], arr[j], arr[k]};
                }
            }
        }

        return combinations;
    }

    // 팩토리얼을 계산하는 메소드
    static int factorial(int n) {
        if (n == 0) {
            return 1;
        }

        int[] table = new int[n + 1];
        table[0] = 1;

        for (int i = 1; i <= n; i++) {
            table[i] = i * table[i - 1];
        }

        return table[n];
    }

    // 테스트 입력 문자열
    static String input1() {
        return "30 42 70 35 90";
    }
}

3차 리팩토링 코드

결과: 통과

모든 조합을 생성하는 대신, 최소 공배수를 효율적으로 계산하도록 코드를 변경하였습니다.

주어진 배열의 모든 세 수의 조합을 찾는 대신, 최소 공배수를 계산할 때 가장 작은 값을 추적하면 됩니다. 이를 위해 삼중 루프를 유지하되,
결과를 즉시 최소값으로 업데이트할 수 있습니다.

package 적어도대부분의배수;

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

public class Main3 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 버퍼로부터 첫줄을 읽어 Arrays.stream을 이용하여 정수 배열로 변환
        int[] intArr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        // 초기 최소값을 최대값으로 설정
        int answer = Integer.MAX_VALUE;

        // 세 수의 모든 조합에 대해 최소 공배수를 계산하고 최소값을 업데이트
        for (int i = 0; i < intArr.length - 2; i++) {
            for (int j = i + 1; j < intArr.length - 1; j++) {
                for (int k = j + 1; k < intArr.length; k++) {
                    int lcmValue = lcm(intArr[i], intArr[j], intArr[k]);
                    if (lcmValue < answer) {
                        answer = lcmValue;
                    }
                }
            }
        }

        System.out.println(answer);
    }

    // 두 수의 최대공약수를 구하는 메소드
    static int gcd(int numA, int numB) {
        while (numB != 0) {
            int temp = numB;
            numB = numA % numB;
            numA = temp;
        }
        return numA;
    }

    // 두 수의 최소공배수를 구하는 메소드
    static int lcm(int numA, int numB) {
        return (numA * numB) / gcd(numA, numB);
    }

    // 세 수의 최소공배수를 구하는 메소드
    static int lcm(int numA, int numB, int numC) {
        return lcm(lcm(numA, numB), numC);
    }
}