알고리즘 코드카타 119 - 숫자 카드 나누기

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

프로그래머스

 

문제 설명
철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려고 합니다.

철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
예를 들어, 카드들에 10, 5, 20, 17이 적혀 있는 경우에 대해 생각해 봅시다. 만약, 철수가 [10, 17]이 적힌 카드를 갖고, 영희가 [5, 20]이 적힌 카드를 갖는다면 두 조건 중 하나를 만족하는 양의 정수 a는 존재하지 않습니다. 하지만, 철수가 [10, 20]이 적힌 카드를 갖고, 영희가 [5, 17]이 적힌 카드를 갖는다면, 철수가 가진 카드들의 숫자는 모두 10으로 나눌 수 있고, 영희가 가진 카드들의 숫자는 모두 10으로 나눌 수 없습니다. 따라서 철수와 영희는 각각 [10, 20]이 적힌 카드, [5, 17]이 적힌 카드로 나눠 가졌다면 조건에 해당하는 양의 정수 a는 10이 됩니다.

철수가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayA와 영희가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayB가 주어졌을 때, 주어진 조건을 만족하는 가장 큰 양의 정수 a를 return하도록 solution 함수를 완성해 주세요. 만약, 조건을 만족하는 a가 없다면, 0을 return 해 주세요.

제한사항

1 ≤ arrayA의 길이 = arrayB의 길이 ≤ 500,000
1 ≤ arrayA의 원소, arrayB의 원소 ≤ 100,000,000
arrayA와 arrayB에는 중복된 원소가 있을 수 있습니다.

 

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

 

철수와 영희가 나눠받은 카드의 숫자들의 모든 약수를 구하기 위해서 최대공약수를 계산하는 함수를 작성한다.

 

 

from functools import reduce

def solution(arrayA, arrayB):

    gcd_a = reduce(gcd, arrayA)
    gcd_b = reduce(gcd, arrayB)

 

reduce를 이용해서 gcd함수를 리스트의 모든 원소에 대해서 적용한다. 따라서 각 카드 목록의 모든 수의 최대공약수를 구할 수 있다.

 

# def solution(arrayA, arrayB):
# 
#     gcd_a = reduce(gcd, arrayA)
#     gcd_b = reduce(gcd, arrayB)

    divisor_a = []
    divisor_b = []

    for a in range(1, gcd_a + 1):
        if gcd_a % a == 0:
            divisor_a.append(a)
    for b in range(1, gcd_b + 1):
        if gcd_b % b == 0:
            divisor_b.append(b)

 

최대공약수의 모든 약수를 구한다. 최대공약수의 약수는 리스트의 모든 원소들의 약수이기 때문이다.

약수들을 저장한 리스트를 각각 생성한 뒤에 gcd_a와 gcd_b의 약수들을 각각 저장한다.

 

# def solution(arrayA, arrayB):
      result_a = 0
      result_b = 0
# 
#     gcd_a = reduce(gcd, arrayA)
#     gcd_b = reduce(gcd, arrayB)
# 
#     divisor_a = []
#     divisor_b = []
# 
#     for a in range(1, gcd_a + 1):
#         if gcd_a % a == 0:
#             divisor_a.append(a)
#     for b in range(1, gcd_b + 1):
#         if gcd_b % b == 0:
#             divisor_b.append(b)

    while divisor_a:
        k = divisor_a.pop()
        for arr_b in arrayB:
            if arr_b % k == 0:
                break
        else:
            result_a = k
        break

    while divisor_b:
        k = divisor_b.pop()
        for arr_a in arrayA:
            if arr_a % k == 0:
                break
        else:
            result_b = k
        break

 

카드 a의 약수들을 순서대로 순회하면서 카드 b의 약수가 될 수 있는지 없는지 검사한다.

가장 상단의 while 반복문은 divisor_a, 즉 카드 a의 약수들을 pop()를 통해서 역순으로(큰수부터) 검사하는 역할을 한다. 조건을 만족하는 수 들 중 가장  큰 수를 출력하는 것이 목적이기 때문에 작업속도를  조금이라도 높이기 위함이다. 순서대로 divisor_a의 원소들을 제거해나가면서 divisor_a의 모든 원소가 제거되었을 경우 조건을 만족한 원소가 하나도 없다는 의미이기 때문에 0을 반환한다.

다음으로 pop()를 통해 추출된 원소 k가 카드 b의 약수인지 아닌지 검사한다. 한번이라도 if 조건문을 만족한다면(= k가 카드 b의 원소의 약수라면) 즉시 반복을 종료하고 다음 약수로 넘어간다. 모든 원소에 대해서 조건을 만족하지 않고 for 반복문이 종료되었다면 해당 수 k는 두 조건을 모두 만족하는 가장 큰 k값이기 때문에 결과에 저장을 하고 반복문 전체를 종료한다.

 

# def solution(arrayA, arrayB):
#     result_a = 0
#     result_b = 0
# 
#     gcd_a = reduce(gcd, arrayA)
#     gcd_b = reduce(gcd, arrayB)
# 
#     divisor_a = []
#     divisor_b = []
# 
#     for a in range(1, gcd_a + 1):
#         if gcd_a % a == 0:
#             divisor_a.append(a)
#     for b in range(1, gcd_b + 1):
#         if gcd_b % b == 0:
#             divisor_b.append(b)
# 
#     while divisor_a:
#         k = divisor_a.pop()
#         for arr_b in arrayB:
#             if arr_b % k == 0:
#                 break
#         else:
#             result_a = k
#         break
# 
#     while divisor_b:
#         k = divisor_b.pop()
#         for arr_a in arrayA:
#             if arr_a % k == 0:
#                 break
#         else:
#             result_b = k
#         break

    return max(result_a, result_b)

 

마지막으로 두 반목문의 결과값중 더 큰 값을 정답으로 출력하면 완료!

 

from functools import reduce


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def solution(arrayA, arrayB):
    result_a = 0
    result_b = 0

    gcd_a = reduce(gcd, arrayA)
    gcd_b = reduce(gcd, arrayB)

    divisor_a = []
    divisor_b = []

    for a in range(1, gcd_a + 1):
        if gcd_a % a == 0:
            divisor_a.append(a)
    for b in range(1, gcd_b + 1):
        if gcd_b % b == 0:
            divisor_b.append(b)

    while divisor_a:
        k = divisor_a.pop()
        for arr_b in arrayB:
            if arr_b % k == 0:
                break
        else:
            result_a = k
        break

    while divisor_b:
        k = divisor_b.pop()
        for arr_a in arrayA:
            if arr_a % k == 0:
                break
        else:
            result_b = k
        break

    return max(result_a, result_b)

 

성공!

 

처음에는 숫자의 범위와 크기 때문에 시간초과가 걸리지 않을까 걱정했지만 다행히 시간 안에 풀리게 되었다. 반복문을 중첩해서 코드를 작성해도 종료조건을 잘 작성하면 시간 문제에서 비교적 자유로운걸까?