2364 - Count Number of Bad Pairs (Java)

 

---

 

문제

https://leetcode.com/problems/count-number-of-bad-pairs/description/

 

 

풀이

문제는 i < j 일 때 j - i != nums[j] - nums[i]. 인 쌍을 몇 개 찾느냐인데

 

이 문제는 반대로 생각해야 쉽게 풀린다. 

 

우선 위 식을 "정리" 해볼 수 있는데, 정리하면

 

nums[j] - j != nums[i] - i 형태로 만들 수 있다.

 

이제 반대로 생각해보자. 총 쌍의 개수에서 우리는 위 조건에 부합하지 않는 쌍을 찾으면 답을 구할 수 있다.

위 조건의 반대는?  j > i 일 때  nums[j] - j == nums[i] - i 이다. 

이 말을 풀어보면 내가 j일 때 나보다 작은 값 i 가 있을때 nums[j] - j == nums[i] - i 를 조건하는 i의 개수를 구하면 된다.

 

[4, 1, 3, 3] 을 보자.

 

우선 각 요소의 값 - 인덱스를 해서 결과를 알아보면

 

[4 - 0, 1 - 1, 3 - 2, 3 - 3] => [4, 0, 1, 0] 이다.

 

j는 i보다 커야하니까 인덱스 1부터 확인해보자.

 

idx : 1 일 때 -> idx 가 1 보다 작으면서 nums[j] - j ( = 0 ) 인 값이 몇개가 있는가 찾는다.

 

위 경우에는 idx 0 을 확인해볼 수 있고, idx 0 은 idx 1 의 값인 0이 아닌 4이기 때문에 조건에 부합하지 않는다.

 

idx 2 경우에도 보면 idx 2 의 값은 1이지만 그 앞의 값들은 4, 0 으로 조건에 부합하는게 없다.

 

마지막으로 idx 3 을 보면 idx 1 이 0으로 값이 같기 때문에 한개를 발견할 수 있고

총 경우의 수 6가지에서 1가지를 뺌으로 원하는 답을 구할 수 있다.

 

마지막으로 현재 내가 j일때 nums[j] - j 와 같은 값을 찾기 위해 앞의 모든 값을 순회해야한다고 생각할 수 있지만,

앞에서부터 hashmap 으로 각 숫자의 개수를 저장해놓으면 나와 같은 값이 몇개 있는지 한번에 구할 수 있다.

 

 

코드

import java.util.*;

class Solution {

    public long countBadPairs(int[] nums) {

        int len = nums.length;
        long cnt = 0L;

        long total = 0L;
        for(int i=1; i<len; i++){
            total += i;
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(nums[0] - 0, 1);

        for(int i=1; i<len; i++){
            int target = nums[i] - i;
            if(map.containsKey(target)){
                cnt += map.get(target);
                map.put(target, map.get(target) + 1);
            } else{
                map.put(target, 1);
            }
        }

        return total - cnt;
    }
}