[Kotlin] LeetCode 1512 : Number of Good Pairs

Number of Good Pairs - LeetCode

배열이 주어졌을때, 같은 숫자인 짝이 몇개 존재하는지 세는 문제입니다.
각 숫자가 배열에 몇개 존재하는지 세고, 자기 자신을 제외한 값을 모두 더해줍니다. 이때 무조건 중복해서 값을 세기에, 구한값을 2로 나눠주면 됩니다.

class Solution {
    fun numIdenticalPairs(nums: IntArray): Int {
        var answer : Int = 0
        for(i in nums) {
            answer += (nums.filter { i == it }.size - 1)
        }
        return answer / 2
    }
}

조금 더 함수형으로 짜봅시다.

nums에 들어있는 정수로 group을 묶어주고, 개수를 기준으로 배열을 만들었습니다. 이제 배열에 들어있는 값은 각 숫자가 들어있는 개수가 됩니다. 이 개수를 기준으로 조합 nC2를 구해 모두 더해주면 O(N)에 문제를 해결할 수 있습니다.

class Solution {
    fun numIdenticalPairs(nums: IntArray): Int {
        val list = nums.groupBy { it }
            .map { it.value.size }
            
        return list.fold(0) {
                total, num -> total + num * (num-1) / 2
            }
    }
}