[프로그래머스/python] N개의 최소공배수

N개의 최소공배수

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

코딩테스트 연습 - N개의 최소공배수

---

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다.

 

예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다.

 

n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

 

---

풀이

지수를 이용해서 최소공배수를 구했습니다.

 

def solution(li):
	y = [2,3,5,7]
	root = {'2':0, '3':0, '5':0, '7':0}
	answer = 1

	for i in range(len(li)):
		j = 0
		r = li[i]

		mt = {v:0 for v in root.keys()}

		while 1:
			if r % y[j] == 0:
				r = r / y[j]
				mt[str(y[j])] += 1
				j = -1

			if j == len(y)-1:
				break

			j += 1

		if r != 1 :                     # 2,3,5,7 을 제외한 소수가 나올 때
			root[str(int(r))] = 0
			mt[str(int(r))] = 1
			y.append(int(r))


		for w in range(len(root)):
			if root[str(y[w])] < mt[str(y[w])]:
				root[str(y[w])] = mt[str(y[w])]
				
	for v,k  in root.items():
		answer *= (int(v)**k)
		
	return int(answer)

 

---

사용된 개념

* 딕셔너리

 

* 제곱 구하기