[Python] [Level 2] N개의 최소공배수

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

프로그래머스

 

 

풀이 (1차시도)

최소 공배수 = 두 수의 곱 / 두 수의 최대 공약수
위의 식이면 되는줄 알고 n개의 곱과 n개의 숫자들의 최대 공약수를 구했는데 오답이였다.

 

Ex) 1, 2, 3의 최소 공배수

[틀린 방법] (내가 오해하면서 한 방법)

1,2,3의 곱 = 6

1,2,3의 최대 공약수 = 1

6 / 1 = 6

 

이게 틀린 방법이다.

 

[맞는 방법]

x,y,z의 곱 = xyz

x,y이 최대 공약수 = A

X,z의 최대 공약수 = B

xyz / B 가 답이 된다.

 

# 최대공약수 = 주어진 자연수들의 가장 큰 공통된 수
# 최소공배수 = 자연수들의 곱 / 최대공약수
def solution(arr):
    answer = 0
    a = 14
    stack = []
    tem = []
    
    sum = 1
    for i in arr:
        # 자연수의 곱 구하기
        sum *= i
        
        # 약수 구하기 => 나머지가 0이 되는게 약수
        for j in range(1 ,i+1):

            if i % j == 0:
                #j는 약수가 된다.
                tem.append(j)
        
        stack.append(tem)
        tem = [] #리스트 비우기
    
    print(stack)
    
    # list를 set으로 바꾸기
    setlist = []
    for i in stack:
        a = set(i)
        setlist.append(a)
    
    #교집합 구하기 -> u는 공약수이다
    u = set.intersection(*setlist)
    # 최대 공약수
    commonFactor = max(u)
    
    answer = sum / commonFactor
    
    return answer

 

 

 

풀이 (2차시도)

숫자를 두개씩 모두 따져서 공약수를 구해야한다.

def yaksu(i):
    tem = []
    
    # 약수 구하기 => 나머지가 0이 되는게 약수
    for j in range(1 ,i+1):

        if i % j == 0:
            #j는 약수가 된다.
            tem.append(j)
    return tem
    

# 최소공배수 = 두수의 곱 / 두수의 최대공약수
def solution(arr):
    answer = 0
    stack = []
    
    for i in arr:
        # list를 set으로 바꾸기
        # 공집합을 구하기 위해서
        stack.append(set(yaksu(i)))
        
        
    length=len(arr)
    
    for i in range(length):
        #i+1이기 때문에 마지막 무시
        if i == length-1:
            continue
        else:
            n = stack[i] & stack[i+1] #공약수
            max_n = max(n) #최대 공약수
            mul = arr[i] * arr[i+1]
            ans = mul / max_n
            if ans != arr[i+1]:
                arr[i+1] = ans
                stack[i+1] = set(yaksu(int(ans)))
            
    answer = ans
    
    return answer