파이썬으로 합이 1이 되는 분수 쌍의 개수 계산하기

각 분수가 [분자, 분모] 형태의 리스트로 표현된 분수 목록이 주어졌다고 가정해 보겠습니다. 여기서 각 리스트는 하나의 분수(분자 / 분모)를 나타내며, 우리는 서로의 합이 정확히 1이 되는 분수 쌍의 개수를 찾아야 합니다.

예를 들어 입력이 다음과 같다면,

fractions = [[2, 7], [3, 12], [4, 14], [5, 7], [3, 4], [1, 4]]

출력은 4가 됩니다. (2/7 + 5/7), (3/12 + 3/4), (3/4 + 1/4), (4/14 + 5/7)의 네 쌍이 모두 합이 1이 되기 때문입니다.

해결 접근 방법

이 문제의 핵심 아이디어는 각 분수를 기약분수로 약분한 뒤, 자신과 합이 1이 되는 '보완 분수'를 이전에 본 적이 있는지 확인하는 것입니다. 분수 x/y와 합이 1이 되려면 상대 분수는 반드시 (y−x)/y여야 하므로, 딕셔너리를 활용하면 효율적으로 쌍을 찾을 수 있습니다.

구체적인 단계는 다음과 같습니다:

• d := 새로운 딕셔너리(맵)
• ans := 0
• fractions의 각 분수 i에 대해 반복:
  • x := i[분자]
  • y := i[분모]
  • g := gcd(x, y)
  • x := x / g, y := y / g (기약분수로 약분)
  • temp_x := y − x, temp_y := y
  • 만약 (temp_x, temp_y)가 d에 이미 존재하면:
    • ans := ans + d[(temp_x, temp_y)]
  • d[(x, y)] := 1 + (d[(x, y)] 값이 있으면 해당 값, 없으면 0)
• ans 반환

예제 코드

더 잘 이해할 수 있도록 파이썬 구현 예시를 살펴보겠습니다.

import math

class Solution:
    def solve(self, fractions):
        d = {}
        ans = 0
        for i in fractions:
            x = i[0]
            y = i[1]
            g = math.gcd(x, y)
            x //= g
            y //= g
            temp_x = y - x
            temp_y = y
            if (temp_x, temp_y) in d:
                ans += d[(temp_x, temp_y)]
            d[(x, y)] = d.get((x, y), 0) + 1
        return ans

ob = Solution()
fractions = [[2, 7], [3, 12], [4, 14], [5, 7], [3, 4], [1, 4]]
print(ob.solve(fractions))

입력

[[2, 7], [3, 12], [4, 14], [5, 7], [3, 4], [1, 4]]

출력

4

동작 원리 정리

이 알고리즘은 먼저 최대공약수(GCD)를 이용해 각 분수를 기약분수로 통일합니다. 이렇게 하면 4/14와 2/7처럼 값은 같지만 표현이 다른 분수도 동일한 키로 처리할 수 있습니다. 이후 현재 분수 x/y와 짝을 이루는 보완 분수 (y−x)/y가 딕셔너리에 몇 번 등장했는지 더해 주면, 중복 없이 합이 1인 모든 쌍을 셀 수 있습니다.

전체 시간 복잡도는 분수 개수를 n, 분자·분모의 최댓값을 M이라 할 때 O(n log M) 수준으로, 모든 쌍을 직접 비교하는 순진한 O(n²) 방식보다 훨씬 효율적입니다.