99클럽 코테 스터디 2/99일차 TIL # 숫자 카드 나누기(챌린저)

문제: 숫자 카드 나누기

출처: 프로그래머스

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

프로그래머스

 

1. 문제 설명

문제 설명
철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 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,0001 ≤ arrayA의 원소, arrayB의 원소 ≤ 100,000,000arrayA와 arrayB에는 중복된 원소가 있을 수 있습니다.

입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
문제 예시와 같습니다.
입출력 예 #3
철수가 가진 카드에 적힌 숫자들은 모두 3으로 나눌 수 없고, 영희가 가진 카드에 적힌 숫자는 모두 3으로 나눌 수 있습니다. 따라서 3은 조건에 해당하는 양의 정수입니다. 하지만, 철수가 가진 카드들에 적힌 숫자들은 모두 7로 나눌 수 있고, 영희가 가진 카드들에 적힌 숫자는 모두 7로 나눌 수 없습니다. 따라서 최대값인 7을 return 합니다.

 

2. 문제 해석

 

3. 문제 풀이

풀이 (1) 97.2/100

 

def solution(arrayA, arrayB):
    
    gcd_A = arrayA[0]
    for i in range(len(arrayA)):
        gcd_A = math.gcd(gcd_A, arrayA[i])
    
    gcd_B = arrayB[0]
    for j in range(len(arrayB)):
        gcd_B = math.gcd(gcd_B, arrayB[j])
    print(gcd_A, gcd_B)
    
    
    if gcd_A % gcd_B != 0 or gcd_B % gcd_A:
        if gcd_A == 1 and gcd_B ==1:
            return 0
        elif gcd_A == 1 and gcd_B !=1:
            for num_A in arrayA:
                if num_A % gcd_B == 0:
                    return 0
            return max(gcd_A, gcd_B)
        else:
            return max(gcd_A, gcd_B)
    else:
        return 0
    
    return answer

전 테스트 중 35번 케이스에 대해 실패.

풀이 (2) 100/100

 

풀이(1)에서 gcd a, b 둘 다 1이 아닌 케이스에 대해서 제대로 나누지 않아 틀림.

해당 부분 수정 후 채점하니 35번 테스트 통과

import math

def solution(arrayA, arrayB):
    
    # 최대 공약수 구하기
    gcd_A = arrayA[0]
    for i in range(len(arrayA)):
        gcd_A = math.gcd(gcd_A, arrayA[i])
    
    gcd_B = arrayB[0]
    for j in range(len(arrayB)):
        gcd_B = math.gcd(gcd_B, arrayB[j])
    # print(gcd_A, gcd_B)
        
    # case-1: gcd 둘 다 1인 경우
    if gcd_A == 1 and gcd_B ==1:
        return 0
    
    # case-2: gcd 둘 중 하나가 1인 경우
    
    
    elif gcd_A == 1 and gcd_B !=1:
        
        # case-2-1: 그 중 하나가, 다른 배열의 값으로 나누어 떨어지는 경우
        for num_A in arrayA:
            if num_A % gcd_B == 0:
                return 0
        return max(gcd_A, gcd_B)

    elif gcd_A != 1 and gcd_B ==1:
        for num_B in arrayB:
            if num_B % gcd_A == 0:
                return 0
        return max(gcd_A, gcd_B)

    # 둘 다 1이 아닌 경우
    else:
        if gcd_A < gcd_B:
            for num_A in arrayA:
                if num_A % gcd_B == 0:
                    return 0
        else:
            for num_B in arrayB:
                if num_B % gcd_A == 0:
                    return 0
            
        return max(gcd_A, gcd_B)
    
    return answer

 

4. 정리

이번 문제는 case를 꼼꼼하게 나누는 것이 중요했다.

 

5. 주요 코드

5.1.1최대공약수, 두 수만 비교할 경우

import math

gcd = math.gcd(a, b)

5.1.2 최대공약수, 여러 수를 비교할 경우

배열 내 수들의 최대 공약수를 구할 경우 가장 처음 숫자를 gcd로 설정하고 나머지들을 순차 비교하는 방식으로 적용

gcd_A = arrayA[0]
for i in range(len(arrayA)):
   gcd_A = math.gcd(gcd_A, arrayA[i])