[프로그래머스][Lv.0] 분수의 덧셈

문제

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

프로그래머스

 

내 풀이 1 - 실패

def solution(denum1, num1, denum2, num2):
    denum = 0
    num = 0

    if num1 > num2:
        num1, num2 = num2, num1
        denum1, denum2 = denum2, denum1

    if num2 % num1 == 0:
      denum = denum1*(num2//num1) + denum2
      num = num2
    else:
      denum = denum1*num2+denum2*num1
      num = num1*num2

    if denum == num:
      denum, num = 1, 1
      
    return [denum, num]

result = solution(1, 2, 1, 2)
print(result)

여기까진 풀었는데 문제에서 기약 분수로 나타냈을 때의 분자와 분모를 구하라고 하길래

기약 분수가 뭔가 찾아봤다.

기약분수: 분자와 분모의 공약수가 1뿐이어서 더이상 약분되지 않는 분수

그럼 애초에 분모의 최소공배수로 구하던가 구한다음 기약분수로 만들라는 말인데 

좋은 해답이 안나 결국 다른 사람의 풀이를 참고했다.

 

내 풀이 2 - 성공

def solution(denum1, num1, denum2, num2):
    denum = denum1*num2 + denum2*num1
    num = num1*num2

    check = True
    while check:
      for i in range(2, num+1):
        if denum%i == 0 and num%i == 0:
          denum, num = denum//i, num//i
          break
      else:
        check = False

    return [denum, num]

result = solution(1, 2, 3, 4)
print(result)

일부러 다른 사람 코드를 대충 봤는데, 그냥 냅다 분모끼리 곱하고 각 분자에 서로의 분모값을 곱해준 뒤

더한 값을 추가로 기약분수로 만들어주면 되는거였다.

기약분수로 만드는 방법은 2부터 분모값까지 나눠서 0이 되는걸로 분자, 분모를 나누고

다시 while문으로 돌아가 반복하며 

만약 하나도 나눈게 없는 시도일 경우 기약분수라 판단하는 식으로 진행했다.

결과는 정답

 

시간복잡도

위 풀이 2의 시간복잡도는 최대횟수가 되려면 for문의 else로 최대한 빠지 않고 2로 계속 나눠 for문을 많이 반복해야 되는데, 

이때마다 range(2, num+1)이 거의 반토막 나니 

O(logN)이라고 할 수 있다. (확실치않음)

 

내 풀이 3

답을 구했지만 더 좋은 방법이 없을까 생각하다가 두 분모를 최소공배수로 만들면 바로 답을 얻을 수 있지 않을까라는 생각이 들었다.

이 최소공배수는 수학적 근거에 의해 두 분모를 곱한 값을 최대공약수로 나누면 구할 수 있다.

즉, 최대공약수를 구하면 금방 해결할 수 있는것이다.

최대공약수 구하는 알고리즘은 인류 최초의 알고리즘으로 유명한데, 배운 내용에 따르면

막대기를 이용해 구하는 방법을 통해 다음과 같이 식으로 나타낼 수 있다고 한다.

이에 대해 정리한 글은 아래 참고

https://4sii.tistory.com/215

최대공약수와 최소공배수의 관계 (유클리드 호제법)

 

이 방법대로 푼 풀이는 다음과 같다.

def solution(denum1, num1, denum2, num2):
    gcd = getGCD(num1, num2)
    lcm = num1*num2/gcd

    denum = denum1*(lcm/num1) + denum2*(lcm/num2)
    num = lcm

    # if denum == num:
    #   denum, num = 1, 1
    # 이게 아니라

    # 이렇게 분자와 분모의 최대공약수를 구해 다시 나눠줘야 되는거였음
    gcd2 = getGCD(denum, num)
    denum = denum/gcd2
    num = num/gcd2

    return [denum, num]

# 최대공약수 알고리즘
def getGCD(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

result = solution(17, 13, 2, 3)
print(result)

분모의 최소공배수를 구해서 더한 것 까지는 좋았는데 

그 이후 더해진 값에 대한 분자, 분모를 다시 최소공배수로 나눠야한다는걸 몰라서 자꾸 문제를 틀리는거였다.

이렇게 최소공배수를 이용한 방법으로도 문제를 풀어봤다.

 

이번에는 최소공배수를 반복문을 통해 구해봤는데 재귀함수로도 구할 수 있으니

다음에 또 최소공배수 관련 문제를 만난다면 재귀함수를 사용해봐야겠다.