C++ ] leetCode 1010 - Pairs of Songs With Total Durations Divisible by 60

 

 

리트코드 1010 문제

 

You are given a list of songs where the ith song has a duration of time[i] seconds.

 

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.

 

 

Example 1:

• 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

 

 

Example 2:

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

 

 

Constraints:

• 1 <= time.length <= 6 * 10^4
• 1 <= time[i] <= 500

 

Two Sum과 약간 비슷한 문제다. 두 노래의 시간 합이 60의 배수가 되는 쌍의 개수를 찾는 문제인데, 두 노래의 나머지를 더한 값이 0 또는 60이 되는 쌍을 찾으면 된다.

 

노래길이를 60으로 나눈 값을 카운팅하기 위에 길이가 60이고 초기값이 0인 벡터 remainders를 만든다. 이 벡터의 인덱스는 0~59의 나머지를 의미하고, 해당 인덱스의 값은 해당 나머지를 가지는 노래의 개수이다.

 

time 배열의 첫번째 요소부터 끝까지 순회하며 먼저 해당 인덱스 노래길이의 나머지 60 값을 구한다.

 

나머지가 0인 경우 이전에 등장한 나머지가 0인 노래와 쌍을 이룰 수 있으므로 remainders[0]을 누적합하고, 나머지가 0이 아닌 경우 remainders[60 - 현재 나머지 값]을 누적합한다.

 

이후 remainders에서 현재 노래의 나머지 인덱스 값을 증가시켜 다음 노래가 쌍을 찾을 때 카운트 될 수 있도록 한다.

 

 

 

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        int count = 0;
        vector<int> remainders(60, 0);
        for(int i = 0; i < time.size(); i++) {
            int remainder = time[i] % 60;
            if(remainder == 0) count += remainders[0];
            else count += remainders[60 - remainder];
            remainders[time[i] % 60]++;
        }

        return count;
    }
};