[leetcode] 1010. Pairs of Songs With Total Durations Divisible by 60

leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/

Pairs of Songs With Total Durations Divisible by 60 - LeetCode

두 수를 더해서 60으로 나눴을 때 나머지가 0인 조합을 구하는 문제입니다.

수를 하나 입력을 때, 기존에 입력한 숫자들 중에 현재의 숫자를 가지고 0을 만들 수 있는 수가 몇 개 존재하는지 확인해 보는 것으로 접근했습니다.

처음에 생각했을 때는 수가 입력될 때마다 map에서 수를 찾고, 카운트를 올리면서, 현재 입력한 숫자와 조합했을 때 0을 만들 수 있는 수가 몇개인지로 접근하려고 했는데,

60으로 나눴을 때의 나머지만 저장해놓고 쓰면 되기 때문에 오직 60개의 값만 저장하고 있으면 되었습니다.

그래서 60개짜리 array로 O(N)에 구현해봤습니다.

leetcode score는 99.7% 입니다.

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int array[] = new int[60];
        int retVal = 0;
        for(int i : time) {
            int n = i % 60;
            retVal += array[n==0 ? 0 : 60-n];
            array[n]++;
        }
        return retVal;
    }
}