N개의 최소공배수

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

 

 

---

느낀점

재귀함수 사용이 아직 익숙하지 않다.

 

배열 길이가 0은 지문에서 없다고 함.

배열 길이가 1일 때 return 1; 은 아니다.

 

생각나는 아이디어로 푸는 방법이 내 머리에서 나온거라서 제일 익숙하지만,

유클리드 호제법을 쓰면 코드가 줄어든다.

---

내가 푼 방식

public class N개의최소공배수 {

	public static void main(String[] args) {
		Solution solution = new Solution();
		int[] arr = {12, 14};
		int result = solution.solution(arr);
		System.out.println(result);

	}

	static class Solution {
		public int solution(int[] arr) {
			int leng = arr.length;
			if (leng == 1) {
				return arr[0]; // 배열이 하나의 요소만 가질 경우 그 요소 반환, 1이 아니다
			}
			int result = 1;

			for (int i = 0; i < leng - 1; i++) {
				int n = arr[i];
				int m = arr[i + 1];

				// n과 m이 1일 경우 [1, 1]을 반환
				if (n == 1 && m == 1) {
					return 1;
				}

				//최대 공약수
				int gcd = gcd(n, m);

				// 최소 공배수 계산
				int lcm = (n * m) / gcd;// 12*14/2 = 84

				arr[i + 1] = lcm;
			}// for end

			return arr[leng - 1];

		}// solution func end

		// 최대 공약수 계산 (유클리드 호제법)
		private int gcd(int a, int b) {// a:12, b:14 -> a:14, b:12 -> a:12, b:2 -> a:2, b:0
			while (b != 0) {
				int temp = b;
				b = a % b;
				a = temp;
			}
			return a;
		}// gcd func end

	}// Solution class end

}// one class end

---

재귀함수 사용

public class Two2 {

    public static void main(String[] args) {
       Solution solution = new Solution();
       int[] arr = {1, 2, 3, 4, 5, 6, 7};
       int result = solution.solution(arr);
       System.out.println(result);

    }

    static class Solution {
       public int solution(int[] arr) {
          int leng = arr.length;
          if (leng == 1) {
             return arr[0]; // 배열이 하나의 요소만 가질 경우 그 요소 반환
          }
          int lcm = arr[0]; //처음 값을 가져옴

          for (int i = 1; i < leng; i++) { // 배열 인덱스1부터 가져옴, 따라서 길이가 leng
             lcm = lcm(lcm, arr[i]);
          }// for end

          return lcm;

       }// solution func end

       // 최대 공약수 계산 (유클리드 호제법)
       private int gcd(int a, int b) {
          while (b != 0) {
             int temp = b;
             b = a % b;
             a = temp;
          }
          return a;
       }// gcd func end

       // 최소 공배수 계산
       private int lcm(int a, int b) {
          return (a * b) / gcd(a, b);
       }

    }// Solution class end

}// one class end

 

---

다른 사람 푼 방식

max값을 효율적으로 키워가면서, 주어진 값으로 다 나뉘어지는 첫번째 값을 리턴한다. 오 좋은 방법인데?

import java.util.*;

class Solution {
    public int solution(int[] arr) {
        int originalMax = 0;
        for (int i = 0; i < arr.length; i++) {
            originalMax = Math.max(originalMax, arr[i]);
        }
        int max = originalMax;
        
        while (true) {
            boolean isLCM = true;
            for (int i = 0; i < arr.length; i++) {//배열에 있는 모든 수로 나눠지는 경우를 찾으려고
                if (max % arr[i] != 0) {
                    max += originalMax;//왜 더할까 했는데 효율적으로 점증하려고 했구나
                    isLCM = false;
                    break;
                }
            }
            if (isLCM) {
                break;
            }
        }
        
        return max;
    }
}