99 Club 2기 | Java | Beginner
1512. Number of Good Pairs
🏷 관련 주제 : Array Hash Table Math Counting
Easy
Given an array of integers nums, return the number of good pairs.
A pair (i, j) is called good if nums[i] == nums[j] and i < j.
Example 1:
Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.
Example 2:
Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.
Example 3:
Input: nums = [1,2,3]
Output: 0
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100
Accepted 776K | Submissions 871K | Acceptance Rate 89.1%
✔ Solution with HashMap
import java.util.HashMap;
class Solution {
public int numIdenticalPairs(int[] nums) {
int answer = 0;
HashMap<Integer, Integer> hm = new HashMap<>();
for (int n : nums) {
int cnt = hm.getOrDefault(n, 0);
hm.put(n, cnt + 1);
}
for (int v : hm.values()) {
answer += v * (v - 1) / 2;
}
return answer;
}
}채점 결과
✔ Solution with Array
class Solution {
public int numIdenticalPairs(int[] nums) {
int answer = 0;
int preIdx = 0;
int cnt;
Arrays.sort(nums);
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i - 1]) {
cnt = i - preIdx;
preIdx = i;
if (cnt > 1) {
answer += cnt * (cnt - 1) / 2;
}
}
}
cnt = nums.length - preIdx;
answer += cnt * (cnt - 1) / 2;
return answer;
}
}채점 결과
✔ Solution with Stream API
import java.util.Arrays;
class Solution {
public int numIdenticalPairs(int[] nums) {
int answer = 0;
int[] nArr = Arrays.stream(nums).distinct().toArray();
for (int n : nArr) {
int cnt = (int) Arrays.stream(nums).filter(x -> x == n).count();
if (cnt > 1) {
answer += cnt * (cnt - 1) / 2;
}
}
return answer;
}
}채점 결과
💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍
📌 오늘 만난 문제 : 매개변수로 주어진 int[] nums에서 nums[i] == nums[j] and i < j를 만족하는 (i, j) 순서쌍을 good이라고 할 때, good인 순서쌍의 개수를 반환하시오.
문제에 관련 주제에 Hash Table이라고 되어 있어서 HashMap을 사용해 문제를 풀어보았다.
good인 순서쌍의 개수는 nums에서 같은 값의 서로 다른 원소를 순서쌍으로 나타낼 수 있는 개수를 의미함으로nums에 존재하는 원소값들 중, 2개 이상이 존재하는 원소를 찾아야 한다.
1. HashMap을 이용하여 nums에 존재하는 값들의 개수를 세자.
HashMap
hm의 Key는원소의 값Value는원소의 개수
HashMap<Integer, Integer> hm = new HashMap<>();
for (int n : nums) {
int cnt = hm.getOrDefault(n, 0);
hm.put(n, cnt + 1);
}같은 값이 2개 이상 존재하는 원소가 good인 순서쌍을 만족하는 경우의 수가 어떻게 되는지 알아보자.
먼저 k, l, m, n이 값을 갖는 원소의 인덱스가 총 4개 존재한다고 가정하자.
(nums[k] = nums[l] = nums[m] = nums[n]이고 k < l < m < n임을 만족한다.)
good인 순서쌍 (i, j)가 i < j를 만족해야하므로
k를 처음 오는 인덱스로 만들 수 있는 good 순서쌍의 개수는 총3개 (= 4 - 1)
((k, l), (k, m), (k, n))
l를 처음 오는 인덱스로 만들 수 있는 good 순서쌍의 개수는 총2개 (= 4 - 2)
((l, m), (l, n))
m를 처음 오는 인덱스로 만들 수 있는 good 순서쌍의 개수는 총1개 (= 4 - 3)
((m, n))
그러므로 위의 경우, good 순서쌍의 개수는 등차수열의 합 공식에 의해
$$(4 - 1) + (4 - 2) + (4 - 3)$
= \frac{(4 - 1) \cdot \left\{(4 - 1) + 1\right\}}{2}
= \frac{(4 - 1) \cdot 4}{2}$$
즉, 공통인 값이 n개인 원소로 만들 수 있는 good 순서쌍의 개수는
$$\frac{n × (n - 1)}{2}$$
2. HashMap hm의 값들을 하나씩 꺼내 answer에 각 원소 개수에 대한 good 순서쌍의 개수를 더하자.
for (int v : hm.values()) {
answer += v * (v - 1) / 2;
}3. answer에 할당된 값을 반환하자.
return answer;💬 무엇을 새롭게 알았는지
한 문제를 여러 방법으로 풀어 보았다.
- HashMap 메서드
getOrDefault()put()values() - Stream API
distinct()filter().count()
