1010. Pairs of Songs With Total Durations Divisible by 60

문제

 - 두 가지 곡 시간의 합이 60으로 나뉘어지는 Pair의 수를 찾아라

 

해결방법

 1. Brute Force를 이용해서 곡 pair의 합이 60으로 나뉘어지는 곡들 찾기

 2. 각 곡들의 시간을 60으로 나누었을 때 나머지 값이 같은 곡이 있다면 +1 해주기.

 

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int output = 0;
        int size = time.length;
        
        for (int i = 0; i < size; i++){
            for(int j = i+1; j < size; j++){
                int totalTime = time[i] + time[j];
                if (totalTime % 60 == 0){
                    output++;
                }
            }
        }
        return output;
        
    }
}

 

첫번째 방법인 Brute Force는 가장 직관적인 알고리즘을 도출해준다. 하지만 Running Time이 O(n²)가 나오므로 Time excceeded가 나와버렸다.

 

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] rem=new int[60];  //to keep count of remainders
        int output=0;    
        for(int t:time){
            int add = (t % 60 == 0) ? rem[0] : rem[60-t%60];
            output += add;
            rem[t%60]++;
        }
        return output;
        
    }
}

 

그래서 생각해낸게 두번째 방법. 각각의 Element를 60으로 나눴을 때 나머지가 같은 Element가 있을 경우 "두 개의 합 / 60"의 나머지 값을 X라고 하자. 60 - X 값이 2면 특정 Element의 Pairs of songs with total durations divisible by 60은 2라는 얘기이다.

 

예를들어 [30,20,150,100,40]를 도입해보자. 처음 두 개 Element의 나머지의 값은 다르기 때문에 output에 아무것도 더하지 않는다. 하지만 세번째 Element인 150을 60으로 나누었을 때 값은 "30". 앞서 30은 첫번째 Element가 나왔을 때의 나머지 값과 동일하기 때문에 이미 rem[30]에는 1이 더해져있으므로 결과적으로 output에는 1이 더해진다. 이러한 값은 30을 어떤 element와 합하고 60으로 나누더라도 한 개의 element만 pair를 만들 수 있다는 얘기다.