프로그래머스 Level2 숫자 카드 나누기 Python

문제 링크

풀이

두가지 조건중 만족하는 숫자 중 가장 높은 숫자를 구하는 문제

1. 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
2. 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

제한사항

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

정답 코드

def solution(arrayA, arrayB):
    # 모든게 나눠지는지 확인하는 함수
    def check1(arr,x):
        for y in arr:
            if y%x !=0:
                return False
        return True
    # 모든게 안나눠지는지 확인하는 함수
    def check2(arr,x):
        for y in arr:
            if y%x ==0:
                return False
        return True
    answer = 0
    mina = min(arrayA)
    minb = min(arrayB)
    arra = []
    arrb = []
    for i in range(2,mina//2+1):
        if mina%i == 0:
            arra.append(i)
    arra.append(mina)
    arra.reverse()
    for i in range(2,minb//2+1):
        if minb %i == 0:
            arrb.append(i)
    arrb.append(minb)
    arrb.reverse()
    for i in arra:
        if check1(arrayA,i):
            if check2(arrayB,i):
                answer = i
                break;
    for i in arrb:
        if answer >= i:
            break
        if check1(arrayB,i):
            if check2(arrayA,i):
                answer = max(answer,i)
                break
    return answer

풀이 설명

리턴해야하는 값은 한 배열의 공약수 중에 다른 배열의 공약수에 포함이 되지 않는 숫자 중 가장 큰 값을 구하는 문제이다.

공약수의 개수가 가장 작은 수를 선택해서 비교를 하는게 빠르지만 최대 50만개의 숫자를 하나씩 확인하면 매우 오래 걸린다.

그래서 공약수의 개수가 작을 확률이 높은 가장 작은 숫자를 기준으로 비교를 한다.

• 배열 A,B 의 가장 작은 숫자의 공약수를 모두 뽑아낸다.
• arra 에는 A의 가장 작은 숫자의 공약수들의 집합 , arrb에는 B의 가장 작은 숫자의 공약수들의 집합이 들어있다.
• 그리고 가장 큰 숫자를 찾아야 하기때문에 오름차순으로 되어있는 배열을 뒤집어 준다.
• check1 함수는 해당 숫자가 배열의 전체 공약수인지 확인하는 함수
• check2함수는 해당 숫자가 배열의 숫자 중 공약수에 포함되는지 확인하는 함수
• A배열의 전체 공약수일 경우 B 배열의 공약수에 포함되지 않는 경우 이면 answer을 해당 공약수로 바꾼후 종료
• B배열에 대해서 위와 같은 행동을 실행

 

처음에는 브루트 포스로 했지만 당연히 시간초과.

입력조건을 보고 이분탐색을 시도했지만 이분탐색으로 할 경우 증가 , 감소 조건을 찾지 못했다.

반례를 생각했을때 60을 기준으로 공약수를 생각해보면

[ 1 , 2 , 3 , 4 , 5 , 6 , 10 , 12 , 15 , 20 , 30 , 60 ]

이렇게 5가지 원소가 있고 이분탐색으로 진행시 모든 원소의 공약수가 아닐시 감소 , 맞을시 증가 라고 조건을 주려고 했지만

우선 10을 먼저 탐색한다고 치고 10이 모든 원소의 공약수가 아닐경우에 감소를 한다.

하지만 더 높은 숫자 12가 모든 원소의 공약수일 가능성도 존재한다.

그래서 이분탐색을 포기하고 위와 같이 풀이가 최선이라고 생각하고 풀었다.