[LeetCode] Pairs of Songs With Total Durations Divisible by 60

time 배열이 주어지고 2개를 더 했을 때 60으로 나눠지는 값이 몇개인지 구하는 문제.
i < j 이다.

Example
Input: time = [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60

Input: time = [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.

1 <= time.length <= 6 * 104
1 <= time[i] <= 500

이 문제는 간단하게 풀면 2중 포문으로 풀 수 있을 것 같다.

const numPairsDivisibleBy60 = (time) => {
    let count = 0;
    
    for(let i = 0; i < time.length - 1; i++) {
        for(let j = i + 1; j < time.length; j++){
            if((time[i] + time[j]) % 60 === 0) {
                count += 1;
            }
        }
    }
    return count;
};

하지만 이 방법은 시간복잡도가 O(N^2)이기 때문에 효율적이지 못 하다.
그래서 더 좋은 코드를 찾아보았다. Discuss를 봤을 때 좋았던 코드를 리팩토링 해보았다.

const numPairsDivisibleBy60 = (times) => {
    const appearMap = {};
    let count = 0;
    times.forEach(time => {
        const mod = time % 60;
        const left = (60 - mod) % 60;
        count += appearMap[left] || 0;
        appearMap[mod] = (appearMap[mod] || 0) + 1;
    });
    
    return count;
};

appearMap을 appear 여부를 체크한다. time을 60으로 나눈 값을 mod에 저장을 하고 left에는 60-mod 를 60으로 나눈 값을 저장한다. time이 40이었으면 left는 20이고 appearMap에 20이 존재할 경우 count를 그 수만큼 증가시키는 것이다.
그 후 mod값이 있다는 의미로 1만큼 증가시킨 값을 appearMap[mod]에 저장한다. 그러면 40이 필요한 숫자인 20, 100... 등의 숫자가 time으로 들어왔을 때 left에 있기 때문에 자기자신이랑 나눠질 수 있는 숫자가 있다고 판단할 수 있다.