[프로그래머스] N개의 최소공배수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

입력받은 리스트 중 앞에서 2개씩 꺼내어 두 수의 최소공배수를 구하고 구한 공배수를 다시 리스트의 제일 앞에 추가하며 최소공배수가 1개가 될 때까지 구한다.

 

1. 구한 공배수를 제일 앞에 추가할 때 appendleft() 함수를 사용하기 위해 리스트를 deque 자료구조로 바꿔 사용해야 하는데 deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
2. 입력받은 리스트를 deque 자료구조로 변환한다. queue = deque(arr)
3. 원소가 1개가 될 때까지 반복한다. while (len(queue) > 1)
4. 앞에서부터 숫자 2개를 꺼내 각각 저장한다. num1 = queue.popleft()  num2 = queue.popleft()
5. 각 수에 임의의 수를 각각 곱하여 곱한 결과가 일치하면 그 수가 최소공배수가 된다. 해당 과정을 위해 각 수에 곱해줄 임의의 수를 생성하고 1로 초기화한다. i = 1  j = 1
6. 각 수와 해당 임의의 수를 곱한 결과가 서로 동일할 때까지 반복한다. while (num1 * i != num2 * j)
7. 만약 앞 수의 곱셈 결과가 더 크면 뒷 수의 임의의 수를 1 증가시킨다. if (num1 * i > num2 * j): j += 1
8. 반면에 뒷 수의 곱셈 결과가 더 크면 앞 수의 임의의 수를 1 증가시킨다. else: i += 1
9. 두 수의 최소공배수를 구했으면 해당 수를 deque의 제일 앞에 추가한다. queue.appendleft(num1 * i)
10. 모든 수의 최소공배수를 구했으면 하나 남은 deque의 제일 앞 원소를 정답에 저장한다. answer = queue[0]

반응형

3. 소스코드

from collections import deque

def solution(arr):
    answer = 0
    
    queue = deque(arr)
    
    while (len(queue) > 1):
        num1 = queue.popleft()
        num2 = queue.popleft()

        i = 1
        j = 1
        while (num1 * i != num2 * j):
            if (num1 * i > num2 * j):
                j += 1
            else:
                i += 1
                
        queue.appendleft(num1 * i)
        
    answer = queue[0]

    return answer