[연습문제 / 프로그래머스] 135807번 : 숫자 카드 나누기

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

 

스스로 푼 문제다!

이해는 어렵지 않았는데, 시간 복잡도 때문에 이에 대해 생각해봐야했던 문제다. 

math.gcd 사용하는 법을 익혀야할 것 같다. 

 

문제 이해 

arrayA 원소의 공약수 중 arrayB의 모든 원소를 나누지 못하는 수를 구하고

arrayB 원소의 공약수 중 arrayA의 모든 원소를 나누지 못하는 수를 구해서

그 중 최댓값을 반환하고, 없다면 0을 반환하면 된다고 이해했다. 

 

풀이 이해

• 각 배열에 대해 모든 원소를 나누는 공약수가 있는지 확인하기 위해 get_common() 함수를 이용했다. 
  • 처음에는 여기서 모든 원소의 약수를 모은 다음 진행했는데, 이렇게 하면 시간초과가 발생하므로 시간을 줄일 수 있는 방법을 생각했다.
  • 배열의 모든 원소를 나눌 수 있는 수라면 배열의 한 원소를 선택해 그것의 약수로 진행해도 된다라는 생각했다. 그래서 가장 큰 원소의 약수를 temp에 저장한다음 그 원소 중에 arr의 모든 원소를 나눌 수 있는 것들을 result에 모은 다음 반환했다. 
• arrayA와 arrayB에 대해 commons_A, commons_B를 구한 다음 길이에 따라 로직을 다르게 했고, 공통된 연산은 operation()함수를 이용했다. 결과는 answer에 저장했다.
• 이렇게 구한 answer는 조건을 만족하는 수이므로 answer에 원소가 없다면 0을, 있다면 최대값을 반환한다. 
• 이때 arrayA = [3], arrayB = [17]인 경우 각 배열의 원소는 본인이 속한 배열의 원소를 다 나누고, 반대는 다 나누지 못하기 때문에 두 수 모두 조건을 만족한다. 이런 경우는 둘 중 최댓값을 반환하는 로직을 추가해야 테스트 두 개를 통과할 수 있다. (edge case)

 

- 정답 풀이 :

풀이가 너무 길다.

다른 풀이 참고해서 약수 구하는 것 등 코드 줄일 수 있는 방법을 생각해봐야겠다.

 

import math

def get_common(arr): #리스트의 모든 원소 약수를 모두 모아서 반환하는 함수 
    temp = []
    arr.sort()
    num = arr[-1]
    for i in range(2, int(math.sqrt(num) + 1)):
        if num % i == 0:
            temp.append(i)
            temp.append(num // i)
            
    result = []
    for i in range(len(temp)):
        flag = True
        for j in range(len(arr)):
            if arr[j] % temp[i] != 0:
                flag = False
                break
        if flag:
            result.append(temp[i])
            
    return result

def operation(arr, commons):
    answer = []
    for i in range(len(commons)):
            flag = True
            for j in range(len(arr)):
                if arr[j] % commons[i] == 0:
                    flag = False
                    break
            if flag:
                answer.append(commons[i])
    return answer
                         
def solution(arrayA, arrayB):
    if len(arrayA) == 1 and len(arrayB) == 1:
        min_num, max_num = min(arrayA[0], arrayB[0]), max(arrayA[0], arrayB[0])
        if max_num % min_num != 0: # 두 수는 소수 관계
            return max_num
    
    commons_A = get_common(arrayA) # A의 모든 원소를 나누는 공약수 
    commons_B = get_common(arrayB) # B의 모든 원소를 나누는 공약수 
    
    answer = []
    if len(commons_A) == 0 and len(commons_B) == 0:
        return 0
    
    elif len(commons_A) == 0:
        answer = operation(arrayA, commons_B)
        
    elif len(commons_B) == 0:
        answer = operation(arrayB, commons_A)
                
    else: 
        answer = operation(arrayA, commons_B)
        answer += operation(arrayB, commons_A)
                      
    if len(answer) == 0:
        return 0 
    else:
        return max(answer)

 

 

- 시도해본 풀이 :

테스트 2 / 3 통과했다. 

import math

def get_common(arr): #리스트의 모든 원소 약수를 모두 모아서 반환하는 함수 
    temp = set()
    for i in range(len(arr)):
        num = arr[i]
        for j in range(2, int(math.sqrt(arr[i])) + 1):
            if num % j == 0:
                temp.add(j)
                temp.add(num // j)
                
    temp = list(temp)
    result = []
    for i in range(len(temp)):
        flag = True
        for j in range(len(arr)):
            if arr[j] % temp[i] != 0:
                flag = False
                break
        if flag:
            result.append(temp[i])
            
    return result

def operation(arr, commons):
    answer = []
    for i in range(len(commons)):
            flag = True
            for j in range(len(arr)):
                if arr[j] % commons[i] == 0:
                    flag = False
                    break
            if flag:
                answer.append(commons[i])
    return answer
                         
def solution(arrayA, arrayB):
    commons_A = get_common(arrayA) # A의 모든 원소를 나누는 공약수 
    commons_B = get_common(arrayB) # B의 모든 원소를 나누는 공약수 
    
    answer = []
    if len(commons_A) == 0 and len(commons_B) == 0:
        return 0
    
    elif len(commons_A) == 0:
        answer = operation(arrayA, commons_B)
        
    elif len(commons_B) == 0:
        answer = operation(arrayB, commons_A)
                
    else: 
        answer = operation(arrayA, commons_B)
        answer += operation(arrayB, commons_A)
                      
    if len(answer) == 0:
        return 0 
    else:
        return max(answer)