คู่เพลงที่ระยะเวลารวมหาร 60 ลงตัวใน Python

ให้ลิสต์เพลง time[i] = ระยะเวลาวินาที หาจำนวนคู่ (i,j) ที่ i<j และ (time[i] + time[j]) หาร 60 ลงตัว

ตัวอย่าง: [30,20,150,100,40] → 3 คู่: (30,150)=180, (20,100)=120, (20,40)=60

ขั้นตอนการแก้ปัญหา

1. ใช้ dictionary remainder นับจำนวนเศษ mod 60 ที่เจอแล้ว
2. ans = 0
3. วนลูปแต่ละ t ใน time:
   • ถ้า t % 60 == 0 และมีเศษ 0 อยู่แล้ว: ans += remainder[0]
   • ถ้ามีเศษ 60 - (t % 60) อยู่แล้ว: ans += remainder[60 - (t % 60)]
   • เพิ่ม remainder[t % 60]
4. คืน ans

ตัวอย่างโค้ด

class Solution(object):
    def numPairsDivisibleBy60(self, time):
        ans = 0
        remainder = {}
        for t in time:
            r = t % 60
            if r == 0:
                ans += remainder.get(0, 0)
            else:
                ans += remainder.get(60 - r, 0)
            remainder[r] = remainder.get(r, 0) + 1
        return ans

ob1 = Solution()
print(ob1.numPairsDivisibleBy60([30,20,150,100,40]))

อินพุต

[30,20,150,100,40]

เอาต์พุต

3

วิธีแก้แบบ Pythonic (ใช้ Counter)

from collections import Counter

def numPairsDivisibleBy60(time):
    rem = Counter(t % 60 for t in time)
    ans = 0
    # คู่ที่ทั้งคู่ mod 60 = 0
    ans += rem[0] * (rem[0] - 1) // 2
    # คู่ที่ mod 60 = 30
    ans += rem[30] * (rem[30] - 1) // 2
    # คู่อื่นๆ: r และ 60-r
    for r in range(1, 30):
        ans += rem[r] * rem[60 - r]
    return ans