728x90
def divList(n):
lst = []
for i in range(2, int(n**(0.5))+1):
while n%i == 0:
lst.append(i)
n = n//i
if n!=1:
lst.append(n)
return lst
def solution(n, m):
A = divList(n)
B = divList(m)
A.append(0)
B.append(0)
GCD = []
LCM = []
i, j = 0, 0
val1, val2 = 1, 1
while A[i]!=0 and B[j]!=0:
if A[i]==B[j]:
GCD.append(A[i])
LCM.append(A[i])
i += 1
j += 1
elif A[i]>B[j]:
LCM.append(B[j])
j += 1
else:
LCM.append(A[i])
i += 1
while A[i] != 0:
LCM.append(A[i])
i += 1
while B[j] != 0:
LCM.append(B[j])
j += 1
for i in GCD:
val1 *= i
for j in LCM:
val2 *= j
return [val1, val2]
<내 풀이 분석>
고등학교 때 배운 소인수분해를 사용한 풀이이다.
1. divList함수로 어떤 값을 소인수분해한 리스트 A, B를 얻는다.
2. 소인수분해 리스트 맨 뒤에 0을 붙인다.
3. A와 B가 가리키는 값 중 하나가 0이 될 때까지 A, B리스트의 값을 하나씩 뽑아 비교한다.
값이 같으면 GCD(최대공약수), LCM(최소공배수) 리스트에 값을 추가하고 인덱스를 1씩 증가
B값이 더 작으면 LCM(최소공배수) 리스트에 값을 추가하고 B의 인덱스를 1 증가
A값이 더 작으면 LCM(최소공배수) 리스트에 값을 추가하고 A의 인덱스를 1 증가
4. 아직 가리키는 값이 0이 아닌 리스트의 값을 LCM리스트에 추가한다.
5. GCD, LCM리스트의 값을 모두 곱한 값을 return한다.
=> 다른 사람들의 풀이는 5줄 내외로 푼 것도 많았는데 나는 50줄이 나왔다.. 좋은 풀이는 아닌 것 같다ㅜㅜㅜ
=> 유클리드 호제법을 사용하면 훨씬 간단하게 풀 수 있다!!
- 최소공배수 = n * m / 최대공약수
+) 유클리드 호제법을 이용한 풀이
def solution(n, m):
c, d = max(n,m), min(n,m)
mul = c*d
while c%d > 0:
tmp = c%d
c, d = d, tmp
return [d, mul//d]
좋아요를 가장 많이 받은 풀이이다.
1. c가 d보다 크도록 값을 수정한다.
2. c와 d를 곱한 값을 미리 저장해둔다
3. 유클리드 호제법을 이용한 while문. c%d==0이 된다면 d가 최대공약수이다.
4. 최대공약수와 최소공배수를 반환
+) 호제법, 재귀호출을 이용한 방법
def getGCD(a, b):
if a%b == 0:
return b
else:
return getGCD(b, a%b)
def solution(n, m):
gcd = getGCD(n, m)
lcm = n*m//gcd
return [gcd, lcm]
재귀호출로 유클리드 호제법을 구현한 방법이다.
역시 수학공식을 이용하는 게 최고인 것 같다.
728x90
'알고리즘 > programmers[1]' 카테고리의 다른 글
[프로그래머스] 자연수 뒤집어 배열로 만들기 (0) | 2022.01.26 |
---|---|
[프로그래머스] 자릿수 더하기: python3 (0) | 2022.01.25 |
[프로그래머스] 시저 암호: python3 (0) | 2022.01.25 |
[프로그래머스] 제일 작은 수 제거하기 (0) | 2022.01.25 |
[프로그래머스] 소수 찾기: python3 (0) | 2022.01.25 |