[Python] 프로그래머스 Lv2_숫자 카드 나누기

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

프로그래머스

 

• 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a 값 구하기
• 조건
  • 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수
  • 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
• arrayA: 철수가 가진 카드에 적힌 숫자들을 나타내는 정수 배열
• arrayB: 영희가 가진 카드에 적힌 숫자들을 나타내는 정수 배열
• 주어진 조건을 만족하는 가장 큰 양의 정수 a를 return
• 만약, 조건을 만족하는 a가 없다면, 0을 return

제한사항

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

 

"""
입출력 예시)

arrayA = [10, 17], arrayB = [5, 20] -> 0
arrayA = [10, 20], arrayB = [5, 17] -> 10
arrayA = [14, 35, 119], arrayB = [18, 30, 102] -> 7
"""

 

# arrayA = [10, 17], arrayB = [5, 20] -> 0

# 철수: [10, 17]
# 영희: [5, 20]

# => 두 조건 중 하나를 만족하는 양의 정수 a는 존재 X

# arrayA = [10, 20], arrayB = [5, 17] -> 10

# 철수: [10, 20]
# 영희: [5, 17]

# -> 철수가 가진 카드들의 숫자는 모두 10으로 나눌 수 있고, 영희가 가진 카드들의 숫자는 모두 10으로 나눌 수 없음

# => 조건에 해당하는 양의 정수 a는 10

# arrayA = [14, 35, 119], arrayB = [18, 30, 102] -> 7

# 철수: [14, 35, 119]
# 영희: [18, 30, 102]

# -> 철수가 가진 카드에 적힌 숫자들은 모두 3으로 나눌 수 없고, 영희가 가진 카드에 적힌 숫자는 모두 3으로 나눌 수 있음 => a = 3
# -> 철수가 가진 카드들에 적힌 숫자들은 모두 7로 나눌 수 있고, 영희가 가진 카드들에 적힌 숫자는 모두 7로 나눌 수 없음 => a = 7

# => 조건에 해당하는 양의 정수 a는 최대값인 7

 

 

## 의사코드 ##

# 철수가 가진 카드의 공약수를 모두 구해 리스트에 삽입
# 영희가 가진 카드의 공약수를 모두 구해 리스트에 삽입

# (공약수 구하기)
# 1) array의 최대공약수를 구함
# 2) 최대공약수의 약수를 구함 

# 리스트를 오름차순으로 정렬
# 리스트의 맨 마지막 요소(리스트에서 제일 큰 값)부터 거꾸로 돌면서 조건이 해당하는지 확인 
# 조건 중 하나라도 해당되면 break

# 조건 확인
#   - 배열의 모든 숫자들이 나눠질 수 있는 경우: 배열의 원소 % a == 0 (나누어 떨어짐)
#   - 배열의 모든 숫자들이 나눠질 수 없는 경우: 배열의 원소 % a > 0 (나누어 떨어지지 x)

 

 

첫 번째 시도

 

import math 
def solution(arrayA, arrayB):
    answer = 0
    divisor = []

    # 철수가 가진 카드의 공약수 구하기
    Anum = math.gcd(*arrayA)
    for i in range(1, Anum+1):
        if Anum % i == 0:
            divisor.append(i)

    # 영희가 가진 카드의 공약수 구하기
    Bnum = math.gcd(*arrayB)
    for i in range(1, Bnum+1):
        if Bnum % i == 0:
            divisor.append(i)

    # 공약수 리스트 중복값 제거 및 오름차순 정렬 
    divisor_sorted = list(set(divisor))
    divisor_sorted.pop(0) # 공약수 리스트에서 1 제거 

    # 리스트의 맨 마지막 요소부터 거꾸로 돌면서 조건이 해당하는지 확인
    while divisor_sorted:
        a = divisor_sorted.pop()
    
        for n in range(len(arrayA)): # len(arrayA) == len(arrayB)
            # 조건 1
            if (arrayA[n] % a == 0) and (arrayB[n] % a > 0):
                return a 
            elif (arrayB[n] % a == 0) and (arrayA[n] % a > 0):
                return a
            else:
                return answer  

    return answer

-> TypeError: gcd expected 2 arguments, got 3

 

• 최대공약수 구하기
  • math.gcd()
  • gcd()에 리스트를 넣는 경우 -> 리스트 앞에 * 붙이고 넣어야 TypeError 안 남
    • => math.gcd(*list)

 

 

 

두 번째 시도

 

# 최대공약수 구하기
def GCD(x, y):
    while y:
        x, y = y, x % y
    return x

def GCD_N(arr):
    num = arr[0]
    for n in arr:
        gcd = GCD(num, n)
    return gcd

# solution
def solution(arrayA, arrayB):
    answer = 0
    divisor = []

    # 철수가 가진 카드의 공약수 구하기
    Anum = GCD_N(arrayA)
    for i in range(1, Anum+1):
        if Anum % i == 0:
            divisor.append(i)

    # 영희가 가진 카드의 공약수 구하기
    Bnum = GCD_N(arrayB)
    for i in range(1, Bnum+1):
        if Bnum % i == 0:
            divisor.append(i)

    # 공약수 리스트 중복값 제거 및 오름차순 정렬 
    divisor_sorted = list(set(divisor))
    divisor_sorted.pop(0) # 공약수 리스트에서 1 제거 

    # 리스트의 맨 마지막 요소부터 거꾸로 돌면서 조건이 해당하는지 확인
    while divisor_sorted:
        a = divisor_sorted.pop()
    
        for n in range(len(arrayA)): # len(arrayA) == len(arrayB)
            # 조건 1
            if (arrayA[n] % a == 0) and (arrayB[n] % a > 0):
                return a 
            elif (arrayB[n] % a == 0) and (arrayA[n] % a > 0):
                return a
            else:
                return answer  

    return answer

-> 첫 번째 시도에서 math.gcd()에 바로 리스트를 삽입해서 에러가 났으니 유클리드 호제법을 이용해서 최대공약수 구함

 

• 유클리드 호제법으로 배열의 최대공약수 구하기

# 유클리드 호제법으로 최대공약수 구하기
def GCD(x, y):
    while y:
        x, y = y, x % y
    return x

# 배열의 최대공약수 구하기
def GCD_N(arr):
    num = arr[0]
    for n in arr:
        gcd = GCD(num, n)
    return gcd

 

-> 코드 실행 결과: 테스트 케이스 2) 〉 [10, 20], [5, 17] 실패

(기댓값: 10, 내 코드 실행 값: 0)

 

arrayA = [10, 20]
arrayB = [5, 17]
solution(arrayA, arrayB)

"""
[1, 2, 5, 10]
[1, 2, 5, 10, 1]
[2, 10, 5]
0
"""

-> divisor_sorted가 오름차순으로 정렬이 안돼서 실패함

 

 

 

세 번째 시도

 

# 최대공약수 구하기
def GCD(x, y):
    while y:
        x, y = y, x % y
    return x

def GCD_N(arr):
    num = arr[0]
    for n in arr:
        gcd = GCD(num, n)
    return gcd

# solution
def solution(arrayA, arrayB):
    answer = 0
    divisor = []

    # 철수가 가진 카드의 공약수 구하기
    Anum = GCD_N(arrayA)
    for i in range(1, Anum+1):
        if Anum % i == 0:
            divisor.append(i)

    # 영희가 가진 카드의 공약수 구하기
    Bnum = GCD_N(arrayB)
    for i in range(1, Bnum+1):
        if Bnum % i == 0:
            divisor.append(i)

    # 공약수 리스트 중복값 제거 및 오름차순 정렬 
    divisor_sorted = sorted(list(set(divisor))) 
    divisor_sorted.pop(0) # 공약수 리스트에서 1 제거 

    # 리스트의 맨 마지막 요소부터 거꾸로 돌면서 조건이 해당하는지 확인
    while divisor_sorted:
        a = divisor_sorted.pop()
    
        for n in range(len(arrayA)): # len(arrayA) == len(arrayB)
            # 조건 1
            if (arrayA[n] % a == 0) and (arrayB[n] % a > 0):
                return a 
            elif (arrayB[n] % a == 0) and (arrayA[n] % a > 0):
                return a
            else:
                return answer  

    return answer

-> 공약수 리스트 중복값 제거 및 오름차순 정렬에서 sorted() 추가

-> 코드 실행 결과: 추가 테스트 케이스 실패

 

 

 

네 번째 시도

 

import math 
def solution(arrayA, arrayB):

    answer = []

    gcd_A, gcd_B = arrayA[0], arrayB[0]
    for a, b in zip(arrayA[1:], arrayB[1:]):
        gcd_A, gcd_B = math.gcd(a, gcd_A), math.gcd(b, gcd_B)
    
    for a in arrayA:
        if a % gcd_B == 0:
            break
        else:
            answer.append(gcd_B)
    for b in arrayB:
        if b % gcd_A == 0:
            break
        else:
            answer.append(gcd_A)

    return max(answer) if answer else 0

-> math.gcd()로 최대공약수를 구하는데 리스트를 바로 적용하는 게 아니라 zip()을 이용해서 2개의 수만 적용

-> 코드 실행 결과: 추가 테스트 케이스 1개 실패

 

 

 

통과한 코드

 

import math 
def solution(arrayA, arrayB):

    answer = []

    # arrayA와 arrayB의 최대공약수 각각 구하기
    gcd_A, gcd_B = arrayA[0], arrayB[0] # arrayA와 arrayB에서 각각 가장 작은 수 
    for a, b in zip(arrayA[1:], arrayB[1:]):
        gcd_A, gcd_B = math.gcd(a, gcd_A), math.gcd(b, gcd_B)
        # gcd_A = arrayA의 첫 번째 원소를 제외한 나머지 원소와 arrayA의 첫 번째 원소(arrayA[0])의 최대공약수
        # gcd_B = arrayB의 첫 번째 원소를 제외한 나머지 원소와 arrayB의 첫 번째 원소(arrayB[0])의 최대공약수
    
    for a in arrayA:
        # 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고(gcd_B), 철수가 가진 카드들에 적힌 모든 숫자도 나눌 수 있는 경우
        if a % gcd_B == 0: # arrayA의 원소가 arrayB의 최대공약수(gcd_B)로 나누어 떨어지는 경우
            break
    # 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고(gcd_B), 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 경우 
    else: # arrayA의 원소가 arrayB의 최대공약수(gcd_B)로 나누어 떨어지지 않는 경우
        answer.append(gcd_B) # answer에 arrayB의 최대공약수(gcd_B) 추가
    
    for b in arrayB:
        # 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고(gcd_A), 영희가 가진 카드들에 적힌 모든 숫자도 나눌 수 있는 경우
        if b % gcd_A == 0: # arrayB의 원소가 arrayA의 최대공약수(gcd_A)로 나누어 떨어지는 경우 
            break
    # 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고(gcd_A), 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 경우
    else: # arrayB의 원소가 arrayA의 최대공약수(gcd_A)로 나누어 떨어지지 않는 경우
        answer.append(gcd_A) # answer에 arrayA의 최대공약수(gcd_A) 추가

    return max(answer) if answer else 0 # answer가 비어있다면 0, 비어있지 않다면 answer의 max 값 반환

-> else문을 for문 밖으로 빼내서 성공

 

 

 

참고) 

 

https://stackoverflow.com/questions/29194588/python-gcd-for-list

Python gcd for list

 

https://codingpractices.tistory.com/34

[Python] 최소공배수, 최대공약수란? 파이썬 알고리즘으로 쉽게 구현하기 / for문, 유클리드 호제법

 

https://keoroo.tistory.com/54

[Python] N개의 수의 최대 공약수, 최소 공배수 구하기

 

https://comdoc.tistory.com/entry/%EC%88%AB%EC%9E%90-%EC%B9%B4%EB%93%9C-%EB%82%98%EB%88%84%EA%B8%B0

숫자 카드 나누기