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;
}
}
Author And Source
이 문제에 관하여(LeetCode: Pairs of Songs With Total Durations Divisible by 60), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wonhee010/LeetCode-Pairs-of-Songs-With-Total-Durations-Divisible-by-60저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)