[LeetCode] 2364. Count Number of Bad Pairs

■ 문제

문제

j - i != nums[j] - nums[i] 가 성립되는 부분 배열의 수를 찾는 함수를 구현하는 문제이다.

 

■ 풀이

처음 풀 때 Constaints 조건을 못보고 완전탐색으로 풀었다가 Time Limit 이 걸렸다.

class Solution {

    public long countBadPairs(int[] nums) {
        int size = nums.length;
        long answer = 0;

        for(int i = 0; i < size - 1; i++) {
            for(int j = i + 1; j < size; j++) {
                if (j - i != nums[j] - nums[i]) {            
                    answer++;
                }
            }
        }

        System.out.println("answer : " + answer);
        return answer;
    }
}

 

최대 10,000 배열이 있기 때문에 완전 탐색으로 풀면 O(N^2) 이라 10000*10000 연산을 해야한다.

이를 해결하기 위해선 조건을 재해석 해야 한다.

 

j - i != nums[j] - nums[i] 를 j-nums[j] != i-nums[i] 로 바꿔 생각해서 중첩반복문을 사용하지 않는 것이 이 문제의 핵심이다.

 

j-nums[j] 은 index - value 이다.

예를들어 1,1,2,1 nums 배열이 있을 경우 index-value 를 적용하면 -1, 0, 0, -2 이다.0,0 인 부분배열은 goodPairs 이고 이를 제외한 나머지는 badPairs 이다.즉, badPairs = Total - goodPairs 를 도출할 수 있다.

 

{index-value : index-value 개수} 인 HashMap 을 사용해서 goodPairs 의 개수를 업데이트하면 전체 badPairs 를 구할 수 있다.

 

class Solution {

    public long countBadPairs(int[] nums) {
        long size = nums.length;
        long badPairs = 0;
        
        HashMap<Integer, Integer> hm = new HashMap<>();

        for(int i=0; i<size; i++){
            int diff = i - nums[i];
            
            int goodPairs = hm.getOrDefault(diff, 0);

            badPairs += i - goodPairs;

            hm.put(diff, goodPairs + 1);
        }
        
        return badPairs;
    }
}

 

여기서 i 는 전체 부분 배열의 수를 의미하는데,

사이즈가 4인 0, 1, 2, 3 인덱스 배열이 있다고 가정할 때, 해당 문제는 (i,j)  만을 부분배열로 사용한다. 즉 두개의 인덱스만 본다.

때문에 i = 0 일때의 부분배열개수는 3개, i = 1 일때의 부분배열개수는 2개, ..... 로 3+2+1 이 Total 개수이다.