- 문제 : 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)