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

문제 링크

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

프로그래머스

문제 설명

지문이 적지는 않네요. 프로그래머스에서는 영희와 철수라고 했지만, 편의상 간단하게 말씀드리자면

"배열 a, b가 있고, 특정 값(정수) c가 있을 때, a의 모든 값을 c로 나눌 수 있으며, b의 모든 값을 c로 나눌 수 없는 c의 최댓값 또는 그 반대의 값을 찾아라"입니다.

예를 들어볼게요.

a = [3, 6, 9]

b = [4, 10]

이 상황에서 특정 값을 3으로 둔다면 a 배열 안에 있는 모든 값을 나눌 수 있으며, b의 모든 값을 나누지 못하는 상황이 됩니다.

해법

c의 최댓값은 반드시 둘 중 하나의 조건을 만족해요.

1. a 안에 있는 값을 모두 나눌 수 있고, b 안에 있는 값을 모두 나눌 수 없다면, c는 a의 최솟값보다 작다.

2. b 안에 있는 값을 모두 나눌 수 있고, a 안에 있는 값을 모두 나눌 수 없다면, c는 b의 최솟값보다 작다.

둘 다가 아니에요. 둘 중 하나만이에요.

 

모든 수를 나눌 수 있어야 하니, 5를 6으로 나눌 수 없듯이, 특정 배열 안에 있는 가장 작은 값보다 같거나 작아야겠죠.

 

그러면, 범위가 조금은 추려졌어요. 하지만 아직까지도 시간 복잡도는 O(N^2)입니다.

각각의 원소가 가질 수 있는 값은 최대 1억인데, 1억부터 0까지 확인하고, 이를 배열의 개수인 N번만큼 반복한다고 하면 시간 초과가 날 거예요.

그렇기에 또 추릴 필요가 있습니다.

 

바로 한 배열의 최솟값의 약수를 구하는 방법입니다. 그러면 1억이란 값의 약수의 개수라 한들, N번만큼은 아닐거예요. 따라서 N의 시간 복잡도가 나오게 됩니다.

풀이 방법

풀이 방법을 정리해볼게요.

참고로 문제에서 주어진 조건인

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

를 조건1과 조건2이라고 표현할게요.

 

1. 각 배열의 최솟값을 구한다.

2. 각 배열의 최솟값의 약수를 구한다.

3. 각각의 약수를 내림차순 정렬한 뒤, 조건1과 조건2를 만족하는 최댓값 c를 각각 확인한다.

4. 두 조건을 비교했을 때 더 높은 값을 반환하는 최댓값 c를 반환한다.

코드

# n의 약수를 배열에 담아 반환
def divisor(n):
    n = int(n)
    divisors = []
    divisorsB = []

    for i in range(1, int(n**(1/2)) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != (n // i):
                divisorsB.append(n // i)
    return divisors + divisorsB[::-1]


# 약수 배열에서 조건1 또는 조건2를 만족하는 가장 큰 값 c 반환하기
# a:모두 나누어 떨어지는 배열
# b:모두 나누어 떨어지지 않는 배열
# arr: 약수 배열
def confirm(a, b, arr):
    for i in arr:
        aTrue = True
        bTrue = True
        for j in a:
            if j % i != 0:
                aTrue = False
                break
        for j in b:
            if j % i == 0:
                bTrue = False
                break
        if aTrue and bTrue:
            return i
    return 0


def solution(a, b):
    answer = 0
    minA = min(a)
    minB = min(b)

    dA = divisor(minA)[::-1]
    dB = divisor(minB)[::-1]

    result1 = confirm(a, b, dA)
    result2 = confirm(b, a, dB)

    answer = max(result1, result2)

    return answer