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

- 이전 블로그에서 2020. 7. 15.  에 본인이 직접 작성한 포스트를 옮겨온 글입니다.

1. 문제분석

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

Pairs of Songs With Total Durations Divisible by 60 - LeetCode

 

난이도 : easy

 

2. 풀이

 

- 첫번째 시도는 Naive 하게 무작정 하나씩 해보는거다.

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        #simple -> try one by one
        count =0;
        for i in range(len(time)-1):
            for j in range(i+1,len(time)):
                if (time[i]+time[j])%60 ==0:
                    count=count+1
        return count

time[0]+ time[1] 다음은 time[0]+ time[2] .. 겹치지 않게 하나씩 다 해본다.

 

그결과는,,

 

run time error!!

테스트케이스 사이즈가 으마으마 하다..ㅎ

Time complexity  O(N²) 으로 통과하려는 생각은 역시나 어림도 없지!

 

 O(N²) -> O(N)으로 줄여보자. 두 값의 합이 60으로 나뉘어 떨어지려면 두 값이 모두 60으로 나뉘어 떨어지거나 나머지의 합이 60이면 된다.

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        #left over ==0 & ==0 
        # or sum of leftover ==60
        memoize = 60*[0]
        for item in time:
            idx = item%60
            memoize[idx]=memoize[idx]+1
        mysum=0
        for i in range(31):
            if i==0 or i==30:
                num= memoize[i]
                mysum= mysum+ num*(num-1)//2
            else:
                mysum= mysum+ memoize[i]*memoize[60-i]
                
        return mysum

나머지로 분류해서 개수를 센다. 나머지가 0인건 몇개인지, 1인건 몇개인지... 그렇게 0~59 까지 개수를 센다.

time의 합이 어떤 값인지는 중요하지 않다. 나머지만 60이면 되고 그 개수를 알아내면 된다. 개수를 알고있으면 sum을 계산해가는 과정은 순열조합니다.

나머지가 1인 값이 N개 , 59인 값이 M이라면  가능한 경우의 수는 N*M이다. (1에서 하나, 59에서 하나를 고르는 것이니까!)  0일때만 특수하다고 생각했는데 생각해보니 30인 경우도 있었다.  이 두 경우는 같은 주머니에서 두번 뽑는 셈이기 때문에 조합.  N * (N-1) /2 가 된다.

N까지 for문을 한번 돌고 30 까지 한번 돌았다. 중첩for문이 없으니까 time complexity = O(N)

 

결과는 정답이다!

 

 

3. 다른 풀이

공식 솔루션은 없는데 hashmap을 써서 푼 사람도 있는것 같다.

 

 

4. 후기 

Naive 한 방식에서 시작해서 O(n)으로 잘 줄여나가서 문제를 풀 수 있었다. 

출처: https://june13.tistory.com/14 [Made for More]