[LeetCode- Part. 1] 3. 총길이 60초짜리 음악 쌍

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

Pairs of Songs With Total Durations Divisible by 60 - LeetCode

 

노래의 길이를 나타내는 배열

-> 총 길이 60초로 나눌 수 있는 노래 쌍의 수 반환

 

두 개 합쳐서 %60==0이면 answer++

---

1. 이중 for문

: O(n^2)

2. 배열 이용

3. Map 이용

: O(m*n)

 

 

1. 이중 For문

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        //음악 쌍 -> 배열과 Map 사용 가능
        
        int answer=0;
        int[] type= new int[time.length];
        
        if(time==null || time.length==0) return answer;
        
        for(int i=0;i<time.length;i++){ 
            int key=time[i]%60;
        }
        //이중 For문 : 타임리밋 발생
        
        
        return answer;
    }
}

-> 타임리밋 발생

 

2. 배열 이용

: type[] 배열 생성 -> 60으로 나누었을 때 나머지가 0이나 30이 되는 경우는 나누어진다.

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        //음악 쌍 -> 배열과 Map 사용 가능
        
        int count=0;
        //나머지가 60미만 인 배열 -> 0부터 59까지 존재
        int[] types= new int[60];
        
        if(time==null || time.length==0) return count;
        for(int i=0;i<time.length;i++){ 
            int key=time[i]%60;
            
            //배열을 이용해 채우기-> 슬라이딩 윈도우
            //: 인덱스에 해당하는 나머지의 배열값을 증가한다.
            types[key]++;
        }
        //나머지가 30이나 0이 되는 경우를 넣는다.
        //: 0,30 그리고 20, 40분 같이 60이 되는 경우의 수
        
        //0이 되는 경우
        if(types[0]>0) count+=types[0] * (types[0]-1)/2;
        
        //30이 되는 경우
        if(types[30]>0) count+=types[30] * (types[30]-1)/2;
        
        //20+40, 1+50 -> 즉 둘이 합쳐서 60이 되는 경우
        for(int i=1; i<30; i++){
            count+=(types[i] * types[60-i]);
        }
        
        return count;
    }
}

 

3. Map 이용

class Solution {
       public int numPairsDivisibleBy60(int[] time) {
       Map<Integer, Integer> map = new HashMap();
		int total = 0;

		for (int t : time) {
			int val = t % 60;
			map.put(val, map.getOrDefault(val, 0) + 1);
		}

		for (int num : time) {
			num %= 60;
			int diff = (60 - num) % 60;

			if (map.containsKey(diff)) {
				int count = map.get(diff);
				if (count == 0 || (diff == num && count == 1))
					continue;
				System.out.println("diff " + diff + " num " + num);
				total += diff == num ? count - 1 : count;
				map.put(num, map.get(num) - 1);
			}
		}
		return total;
    }
}

 

 

+) Two Sum 문제처럼 풀기

 

class Solution {
       public int numPairsDivisibleBy60(int[] time) {
        int c[]  = new int[60], res = 0;
        for (int t : time) {
            res += c[(600 - t) % 60];
            c[t % 60] += 1;
        }
        return res;
    }
}

 

class Solution {
       public int numPairsDivisibleBy60(int[] time) {
        int c[]  = new int[60], res = 0;
        for (int t : time) {
            res += c[(60 - t % 60) % 60];
            c[t % 60] += 1;
        }
        return res;
    }
}