leetcode 1010. Pairs of Songs With Total Durations Divisible by 60

문제

 

 

풀이

주어진 리스트에서 두 숫자의 합이 60으로 나누어떨어지는 쌍의 개수를 찾는 문제를 해결한다.

이를 위해 각 숫자를 60으로 나눈 나머지를 활용하여 효율적으로 계산한다.

우선, 딕셔너리를 사용해 각 숫자를 60으로 나눈 나머지 값들의 개수를 센다.

이후, 특정 숫자의 나머지 값과 더했을 때 60이 되는 숫자의 개수를 곱하여 가능한 쌍의 개수를 구한다.

예를 들어, 나머지가 10인 숫자가 3개 있고, 나머지가 50인 숫자가 2개 있다면, 이들은 각각 짝을 이룰 수 있으므로

3 × 2 = 6개의 쌍이 만들어진다. 이런 방식으로 나머지 값이 1과 59, 2와 58처럼 서로 합이 60이 되는 쌍을 모두 계산한다.

특별한 경우로, 나머지가 0이거나 30인 숫자들은 같은 나머지 값끼리만 짝을 이룰 수 있다. 따라서, 이들의 개수를 조합 공식(조합의 개수 구하는 방법)을 이용해 계산하여 추가한다.

이 방법을 사용하면 모든 가능한 쌍을 효율적으로 계산할 수 있으며, 시간 복잡도는 O(N)이다.

 

코드

from collections import defaultdict
import math
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        d = defaultdict(int)
        for i in time:
            d[i % 60] += 1
        answer = 0
        for i in range(1,30):
            answer += (d[i] * d[60-i])

        if d[0]>1:
 
            answer += (d[0]*(d[0]-1))//2

        if d[30]>1:
            answer += (d[30]*(d[30]-1))//2       
        return answer