각 분수가 숫자(분자/분모)를 나타내는 개별 목록[분자, 분모]인 분수 목록이 있다고 가정합니다. 합이 1인 분수 쌍의 수를 찾아야 합니다.
따라서 입력이 분수 =[[2, 7],[3, 12],[4, 14],[5, 7],[3, 4],[1, 4]]인 경우 출력은 (2/7 + 5/7), (3/12 + 3/4), (3/4 + 1/4), (4/14 + 5/7)이 4쌍이므로 4가 됩니다. 1.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- d :=새 지도
- ans :=0
- 각 분수 i에 대해 다음을 수행합니다.
- x :=i[분자]
- y :=i[분모]
- g :=(x, y)의 gcd
- 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)
- 반환
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시 코드
class Solution:
def solve(self, fractions):
import math
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