[프로그래머스 Lv.2] N개의 최소공배수.java

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

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요. 

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

---

🔑 풀이

최소공배수는 각 수를 소인수분해한 후 지수가 높은 인수끼리 곱하여 구한다는 원리 이용

ex) 2(2), 6(2 * 3), 8(2^3), 14(2 * 7)의 최소 공배수는 168(2^3 * 3 * 7)

1. 각 수를 소인수분해하여 HashMap<소인수, 소인수의 개수(=지수)>를 ArrayList로 저장한다.
2. 소인수 중 가장 큰 지수를 가진 값을 새로운 HashMap<소인수,지수>로 저장한다.
3. 각 소인수^지수를 곱하면 최소공배수가 된다.

import java.util.*;
import java.util.Map.Entry;

public class Solution {
	public static int solution(int[] arr) {
		int answer = 1;

		// al: 각 수의 hm(소인수분해 결과)을 저장할 arrayList
		ArrayList<Map<Integer, Integer>> al = new ArrayList<>();

		// 소인수분해
		for (int num : arr) {
			// hm: 각 수를 소인수분해한 것. <소인수, 지수>
			Map<Integer, Integer> hm = new HashMap<Integer, Integer>();
			int i = 2;
			while (num != 1) {
				if (num % i == 0) {
					num /= i;
					if (hm.containsKey(i)) { // 이미 저장된 인수라면 지수를 증가시킨다
						hm.replace(i, hm.get(i) + 1);
					} else { // 인수를 저장한다
						hm.put(i, 1);
					}
				} else {
					i++;
				}
			}
			al.add(hm);
		}

		// 가장 큰 지수를 찾아 nhm에 새로 저장한다 
		Map<Integer, Integer> nhm = new HashMap<Integer, Integer>();
		for (int i = 0; i < al.size(); i++) {
			for (Entry<Integer, Integer> entrySet : al.get(i).entrySet()) {
				int key = entrySet.getKey(), value = entrySet.getValue();
				if (nhm.containsKey(key)) {
					if (nhm.get(key) < value) {
						nhm.replace(key, value);
					}
				} else {
					nhm.put(key, value);
				}
			}
		}

		// 모두 곱하여 최소공배수를 만든다 
		for (Entry<Integer, Integer> entrySet : nhm.entrySet()) {
			for (int i = 0; i < entrySet.getValue(); i++) { 
				answer *= entrySet.getKey();
			}
		}

		return answer;
	}
}

---

이때까지 풀었던 문제 중에 알고리즘을 제일 오래 고민하고 풀었다...

왜냐면 최소공배수를 어케 구하는 건지 까먹음(최소공배수 구하는 방법이라고 검색했더니 초등학교 5학년 문제라고 나옴 ㅋ)

근데? 소인수를... 다 구해서 .. 지수를 .. 비교해서.. 풀면 진짜 초딩 그자체일 것 같아서 고민했다..

하지만? 다른 방법은 도저히 생각이 안나서 저렇게 풀었음 ㅎㅁㅎ..

그래도? 저 방법대로 한번만에 풀어냈다는 ~.~