[Leetcode] 1010. Pairs of Songs With Total Durations Divisible by 60 (C++)

문제

1010. Pairs of Songs With Total Durations Divisible by 60

코드

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        int map[60] = {};
        int result = 0;
        
        for(auto x:time){
            int t = x % 60;
            int y = (60 - t)%60;
            result += map[y];
            map[t]++;
        }
        return result;
    }
};

접근

쉽게 생각하면 모든 경우를 다 살펴보면 답을 구할 수 있기 때문에 brute force로 접근하면 답은 쉽게 구할 수 있다. 하지만 주어진 배열의 길이를 보면 이런 시간복잡도 O(N^2)의 풀이는 시간초과가 날 것임이 자명하다. 따라서 다른 풀이가 필요했다. 사실 60의 배수만 되면 되는 것이기 때문에 수의 크기보다 60으로 나눈 나머지의 값이 더 중요하다. 따라서 현재 살피는 값과 매치해서 60이 되는 값의 개수를 더해주면 한 번의 배열 스캔으로도 답을 구할 수 있다.