숫자카드 나누기

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

프로그래머스

문제설명 :

두 리스트가 주어지는데 한리스트에선 모든 숫자를 나눌수 있고, 다른 리스트에선 모든숫자에 나누어 지지 않는 숫자중 가장 큰수를 구하여라.

 

소요시간:

30분 

난이도2

 

1차시도:

import math
import heapq as hp

	
def solution(arrayA, arrayB):
	A = arrayA[0]
	B = arrayB[0]
	
	for a in arrayA[1:]:
		A = math.gcd(A,a)
	for b in arrayB[1:]:
		B = math.gcd(B,b)
	if A*B == 1: #만약 둘다 최대공약수가 1이라면 0을 리턴
		return 0
	q = []
	#리스트에 후보군을 넣기
	for i in range(2,max(A+1,B+1)):
		if A%i == 0: #1이상의 i는 A의 공약수
			hp.heappush(q,(-i,'A'))
		if B%i == 0:
			hp.heappush(q,(-i,'B'))
	piv = 1
	while q:
		num , ch = hp.heappop(q) #제일큰것부터 꺼내기
		num = -num
		if ch =='A':
			for b in arrayB:
				if b%num==0:
					piv = 0
					break
		if ch =='B':
			for a in arrayA:
				if a%num==0:
					piv = 0
					break	
		if piv : #만약에 나머지 가 나누어 떨어지는게 하나도 없다면 			
			return num
	return 0 #while문다돌았는데도 없다면

먼저 두 리스트를 앞에서 부터 두개씩 비교해서 전체의 최소 공배수를 구한후,

(세 숫자이상의 최소공배수는 두 숫자씩 최소공배수를 구하고 그 숫자와 다른숫자들의 최소공배수를 구하면됨)

 

A,B상관없이 조건에 만족하는 가장 큰수를 찾아야 하기 때문에, heap을 사용해 A,B의 최소공배수의 공약수들을 구분하여 넣어주고(heapq은 작은수 부터 반환하기 때문에, -를 붙여 넣어주었는데 생각해보니 순환하며 리스트의 내부에 숫자를 push할 일이 없으니 그냥 리스트에 넣어놓고 한번에 sort()를 하는 편이 더 나았겠다는 생각이 든다.

 

그후, 큰수부터 꺼내며, A의 최소공배수의 약수일 때는 B를 순환하며 나누어떨어지는것을 확인하고, 반대에 경우도 확인하며, 가장 큰 수가 나온다면, 바로 끝내고 반환합니다. 

 

다른 사람의 풀이:

다른사람 풀이를 보기전 짧게 reduce함수와 all함수에 대해 예시를 통해 알아보면, 

 

from functools import reduce

result = reduce(lambda x, y: x+y, [1, 2, 3, 4, 5], 100)
print(result) #115

다음과 같은데 functools에 있는 함수이며, 첫번째엔 함수, 두번째엔 iterable, 세번째엔 initializer가들어가고 안들어간다면 기본값은 None입니다. 위 예시에선 100이라는 초기값을 주었기 때문에 100부터 1을 더하고 그 값에 2를...해서 마지막 5까지더해 115를 출력하게 됩니다. 만약 마지막 100을 없앴다면 초기값을 안주었기 때문에 15를 출력할것 입니다.

 

print(all([True, False, True, True, True])) # False
print(any([True, False, False, False, False])) # True

all함수 그리고 비슷한 성격의 any 함수도 살펴보면, all함수는 말그대로 모든 것이 True일때만 True를 반환 하는 함수 인데, 위 예시에선 False가 하나 껴있기 때문에, False가 출력되고, any함수역시 말 그대로 하나라도 True인 값이 존재한다면, True를 반환하는 함수 입니다. 

 

이제 풀이를 살펴보면

from functools import reduce
from math import gcd


def solution(nums1, nums2):
    gcd1, gcd2 = reduce(gcd, nums1), reduce(gcd, nums2)
    answer = []
    if all(each % gcd2 for each in nums1):
        answer.append(gcd2)
    if all(each % gcd1 for each in nums2):
        answer.append(gcd1)
    return max(answer) if answer else 0

gcd1,gcd2에 reducd함수와 gcd함수를 이용해 한번에nums1과 nums2의 최소 공배수를 찾고,

만약 gcd2에 대해  모든 nums1이 나누어지지 않는다면 (나누었을떄 0이아니라면)  gcd2를 넣고

반대로도 한후 두값중 큰값을 반환했습니다. 

 

피드백:

위 코딩을 보고나니 제코딩에서 GCD_A값이 array_B에대해 나누어 떨어지는게있다면 그 공약수를 넣어 확인했는데, 특정값이 만약 나누어 떨어진다면 그 공약수 역시 당연히나누어 떨어지기 때문에 제 코드중 공약수에 관한부분은 삭제해도 무방합니다.