Programmers / 숫자카드 나누기 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 숫자카드 나누기 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/135807

프로그래머스

문제 설명

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

1. 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
2. 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 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에는 중복된 원소가 있을 수 있습니다.

---

입출력 예arrayAarrayBresult

[10, 17]	[5, 20]	0
[10, 20]	[5, 17]	10
[14, 35, 119]	[18, 30, 102]	7

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 문제 예시와 같습니다.

입출력 예 #3

• 철수가 가진 카드에 적힌 숫자들은 모두 3으로 나눌 수 없고, 영희가 가진 카드에 적힌 숫자는 모두 3으로 나눌 수 있습니다. 따라서 3은 조건에 해당하는 양의 정수입니다. 하지만, 철수가 가진 카드들에 적힌 숫자들은 모두 7로 나눌 수 있고, 영희가 가진 카드들에 적힌 숫자는 모두 7로 나눌 수 없습니다. 따라서 최대값인 7을 return 합니다.

---

나의 풀이 - 첫 풀이 시간초과

 

리스트를 너무 복잡하게 다루어서 시간 초과가 났었다.

def yaksu(num):# 약수를 구하는 함수식
    y_list = []
    for i in range(2,num+1):
        if num % i == 0:
            y_list.append(i)
    return y_list

def check(array,nums):
    for num in nums:
        for i in array:
            if i % num != 0:
                return num
            else:
                break
                
    return 0
    
        
# 약수 중에서 조건을 만족하는 수 중에 가장 큰 양의 정수 구하기
def solution(arrayA, arrayB):
    answer = 0
    arrayA = [i for i in arrayA if i not in arrayB]
    arrayB = [i for i in arrayB if i not in arrayA]
    a = set()
    b = set()
    # 공약수 구하기
    for i in arrayA:
        if a:
            a = a & set(yaksu(i))
        else:
            a.update(yaksu(i))
    
    for i in arrayB:
        if b:
            b = b & set(yaksu(i))
        else:
            b.update(yaksu(i))
    
    a_list = sorted([i for i in a if i not in b],reverse = True)
    b_list = sorted([i for i in b if i not in a],reverse = True)
    
    resultA = check(arrayA,b_list)
    resultB = check(arrayB,a_list)
    
    
    return 0

최대 공약수를 구할때 시간 초과가 나지 않기 위해서는 최대공약수를 구하는 방법중에

유클리드 호제법을 사용해야한다.

 

파이썬 라이브러리는 math 모듈을 통해 gcd 를 구하는 방법을 제공한다.

 

최대공약수를 구하는 법

기본적인 방법

def gcd(a, b):
    for i in range(min(a, b), 0, -1):
        if a % i == 0 and b % i == 0:
            return i

 

 

유클리드 호제법 사용

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

# or

def gcd(a, b):
    if a % b == 0:
        return b
    elif b == 0:
        return a
    else:
        return gcd(b, a % b)

 

 

파이썬 math 라이브러리 사용

import math
a, b = 10, 15
math.gcd(a, b)  # 5

 

 

최종 풀이

from math import gcd

        
# 약수 중에서 조건을 만족하는 수 중에 가장 큰 양의 정수 구하기
def solution(arrayA, arrayB):
    answer = 0
    a_gcd = 0
    b_gcd = 0
    
    for i in arrayA:
        a_gcd = gcd(a_gcd,i)
    for i in arrayB:
        b_gcd = gcd(b_gcd,i)
    
    for i in arrayA:
        if i % b_gcd == 0:
            b_gcd = 1
            
    for i in arrayB:
        if i % a_gcd == 0:
            a_gcd = 1
                
    if a_gcd == 1 and b_gcd == 1:
        return 0
    
    return max(a_gcd,b_gcd)

---

※ 알아야 할 것

- math 모듈에서 gcd 인자값에 0을 넣으면 gcd(0,num) = num의 최대공약수가 나온다.