LeetCode: Pairs of Songs With Total Durations Divisible by 60

문제 풀이

주어진 array 요소들을 짝 지어 합한 값이 60으로 나눠서 나머지가 없는 경우의 수를 return하는 문제였다.
즉, 두 요소를 합한 값이 120여도 180여도 유효한 짝이다.

우선 주어진 array들의 요소들을 60으로 나눈 나머지로 변환하여 저장했다.
나머지 1~29까지 돌면서 31~59까지의 나머지의 곱을 answer에 더했다.

나머지가 0인 경우와 30인 경우는 위와 다른 조건이라 생각해 이후에 처리했다.
위의 경우는 갯수들의 곱으로 경우의 수를 구할 수 있지만 0과 30은 다르다.
우선 0과 30에는 갯수가 2개 이상여야 한다는 조건이 있다.
2개 이상이라면 가능한 짝의 갯수가 피보나치로 늘어난다.
2개 -> 1쌍
3개 -> 3쌍
4개 -> 6쌍
5개 -> 10쌍
...
이런 식으로!
그래서 갯수를 입력하면 피보나치 값을 return 하는 pi()함수를 추가했다.

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] timesCount = new int[60];
        for(int i = 0; i < time.length; i++) {
            int t = time[i] % 60;
            timesCount[t]++;
        }
        int answer = 0;
        for(int index = 1; index < 30; index++) {
            answer += (timesCount[index] * timesCount[60 - index]);
        }
        if(timesCount[0] > 1) {
            answer += pi(timesCount[0]);
        }
        if(timesCount[30] > 1) {
            answer += pi(timesCount[30]);
        }
        return answer;
    }
    
    public int pi(int count) {
        int answer = 0;
        int diff = 1;
        for(int c = 2; c <= count; c++) {
            answer += diff;
            diff++;
        }
        
        return answer;
    }
}

좋은 웹페이지 즐겨찾기