공부하는허딩크 : https://www.youtube.com/live/KtmItpIeYu4?feature=shared
정말 짜증나는 문제였다.
처음 프로그래머스로 파이썬 코딩 테스트 연습을 하다가 몇 가지 문제에 막혀서 백준에서 다시 기초를 밟으면서 전체적으로 복습을 진행했다.
그 이후 백준으로 돌아와서 실버문제에서 조금 고민하면 그래도 웬만큼 풀렸는데 LV0짜리가 계속 풀리지 않았다.
여기에 내 문제점이 있었다. 문제에서 소인수가 가장 중요한 개념인데 그 개념을 놓치고 문제를 해결하려고 하니 풀리지 않았다. (=> 이것도 다른 사람 풀이에서는 필요 없는 개념이다.)
일단 소인수란 정수를 소수들의 곱으로 표현할 때 사용되는 소수들을 의미한다. 예를 들어 어떤 정수를 소수들의 곱으로 나타내면 그 소수들을 소인수라고 한다.
소인수 분해 : 60 // 2 = 30 // 2 = 15 // 3 = 5 ==> 2 * 2 * 3 * 5
<첫번째 시도 : 틀렸습니다.>
이때까지만해도 최대공약수를 얻기 위한 알고리즘을 모르고 별도의 최대공약수를 찾기 위한 코드를 작성했다.
그 다음 기약분수의 분모를 찾고, 그 분모의 약수를 찾아준다음 그 약수에 2와 5가 있는지 여부를 확인했다.
단, 여기서 2와 5를 제외한 나머지 예를 들어 3이 2와 5와 더불어 약수에 있을때 정상적인 답이 나오지 않는다.
#첫번째 시도 : 일단 마지막 2와 5만 남기는 작업은 하지 않음 : 런타임오류 없음 : 단 몇가지 케이스 실패
def solution1(a, b):
answer = 1
a_num = []
b_num = []
max_nums = []
#최대 공약수 찾기
for i in range(1, a + 1):
if a % i == 0:
a_num.append(i)
for i in range(1, b + 1):
if b % i == 0:
b_num.append(i)
for i in a_num:
for j in b_num:
if i == j:
max_nums.append(i)
print(max_nums)
#기약분수 값 찾기
temp = b // max(max_nums)
# if temp == 1:
# answer = 2
limit = [2, 5]
#소인수 구하기 : 요걸 어떻게 풀지 모르겠네.
temp_list = []
for i in range(2, temp + 1):
if temp % i == 0:
temp_list.append(i)
print(temp_list)
for i in temp_list:
if i not in limit:
answer = 2
return answer
<두번째 시도 : 맞을리가 없지>
정수의 약수를 별도 함수를 통해서 구해주는 것으로 기존 첫번째 코드와 다를게 없다.
여기서도 유한소수를 찾을 때 5와 2만 고려해서 다른 소수가 약수일때를 고려하지 못했다,
즉, b = 12일 경우 소인수는 2, 3이다. 그럼 무한소수로 구분되어야 하나 유한소수로 구분된다. (오류)
def solution3(a, b):
a_num = temp(a)
b_num = temp(b)
equal = []
for i in a_num:
for j in b_num:
if i == j:
equal.append(i)
max_equal = max(equal)
print(max_equal)
# final = b // max_equal
# condition = [2, 5]
answer = 2
if (b // max_equal) % 5 == 0 or (b // max_equal) % 2 == 0:
answer = 1
return answer
def temp(num):
answer = []
for i in range(1, num + 1):
if num % i == 0:
answer.append(i)
return answer
<세번째 시도 : 틀렸습니다.>
이것저것 하다가 시간이 흘러 다른 문제에서 유클리드호제법을 알게 되었다.
최대공약수를 쉽게 구할 수 있었지만, 2와 5을 걸러내는 코드에 문제가 있다.
#유클리트호제법 이제는 알고 있음 => 지금 푼다면???? => 그래도 이거 어렵네..[2와 5을 어떻게 풀어내야 할까?]
def solution4(a, b):
answer = 0
max_num = math.gcd(a, b)
deno = b // max_num
print(max_num)
for i in range(2, deno):
if deno % i == 0:
if i % 2 != 0 or i % 5 != 0:
answer = 2
break
else:
answer = 1
return answer
<네번째 시도 : 틀렸습니다.>
전체적인 방향이 잘못된 길로 들어가서 계속 헤매고 있다.
#내가 지금 설계한 소인수 구하기는 20일 경우 [2, 4, 5, 10] 이렇게 나와서 4일때 바로 answer = 2로 가서 break걸림
def solution5(a, b):
answer = 0
temp = [2, 5]
max_num = math.gcd(a, b)
deno = b // max_num
print(max_num)
for i in range(2, deno):
if deno % i == 0 and i not in temp:
answer = 2
break
else:
answer = 1
return answer
<다섯번째 시도 : 틀렸습니다.>
제일 아쉬웠던 코드이다. 거의 맞았는데 정수도 유한소수로 구분하는 것을 놓치고 있었다.
#91.7점 (3개의 테스트에서 실패)
#와 이게 잘 안풀리네?? 내가 지금 소인수를 잘못이해하고 있음
#소인수는 어떤 정수의 약수들 중에서 소수인 것들을 소인수라고 한다.
# 즉, 어떤 정수에서 소인수가 2와 5만 있을때, 다른 약수들은 있어도 상관 없고, 소인수가 2또는 5만 있을때
# 유한소수라고 한다.
import math
def Prime(a):
if a <= 1:
return 0
if a <= 3:
return 1
if a % 2 == 0 or a % 3 == 0:
return 0
p = 5
while p * p <= a:
if a % p == 0 or a % (p + 2) == 0:
return 0
p += 6
return 1
def solution7(a, b):
answer = 2
temp = b // math.gcd(a, b)
for i in range(2, temp + 1):
if temp % i == 0 and Prime(i) and (i == 2 or i == 5):
answer = 1
print(i)
elif temp % i == 0 and Prime(i) and (i != 2 or i != 5):
answer = 2
return answer
<여섯번째 시도 : 통과>
겨우 통과했다.
0. 일단 a % b == 0이면 정수임으로 유한소수소 return 1을 해준다.
1. 소수 판별 함수를 만들고.
2. 최대공약수를 구해서 기약분수를 만들고.
3. 기약분수의 분모인 b의 약수중에서 소수인 것들을 temp 리스트에 넣어서
4. 길이에 따라 조건을 줘서 2와 5를 매칭해서 답을 찾는다.
import math
def Prime(n):
if n <= 1:
return 0
if n <= 3:
return 1
if n % 2 == 0 or n % 3 == 0:
return 0
p = 5
while (p * p) <= n:
if n % p == 0 or n % (p + 2) == 0:
return 0
p += 6
return 1
#이 문제 짜증나네?? 95.8점_2문제 실패 => 정수도 유한소수 3500/500 = > 7/1 ==> 유한소수로 나타내야함
def solution(a, b):
answer = 0
if a % b == 0: #이거 추가함
return 1 #이제까지 문제를 잘못알고 있었네. 정수는 유한소수 => 9, 9는 1이 출력되어야함
b = b // math.gcd(a, b)
temp = []
for i in range(b + 1):
if Prime(i) and b % i == 0:
temp.append(i)
if len(temp) == 0: #이거 필요 없음
answer = 2
elif len(temp) == 1 and (2 in temp or 5 in temp):
answer = 1
elif len(temp) == 2 and 2 in temp and 5 in temp:
answer = 1
else:
answer = 2
return answer
<다른사람풀이 참고>
나는 전혀 생각하지도 못한 방법이 있네???
소수판별도 필요없이, 일단 기약분수의 b를 구해서 2와 5로 계속 나눌 수 있을때 까지 나눈 후
b가 1이 되면 그건 2와 5로만 나누어 떨어졌다는 의미니까 유한소수, 1이외의 나머지 값이 있으면 무한소수로 구분했다.
#How to find this rule?
import math
def solution(a, b):
b //= math.gcd(a, b)
while True:
if b % 2 == 0:
b //= 2
elif b % 5 == 0:
b //= 5
else:
break
return 1 if b == 1 else 2
이렇게도 가능하다. 와... 이런 정답이 어떻게 나오는지.... 진짜 신기하네.
def solution(a, b):
b //= math.gcd(a, b)
while b % 2 == 0:
b //= 2
while b % 5 == 0:
b //= 5
return 1 if b == 1 else 2