[LeetCode] 532번 문제를 풀어보았다. (ft. java)

2022년 2월 09일 수요일 - 오늘 너무 졸렸다아아....

오늘 올려볼 문제는 532번 K-diff Pairs in an Array 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

오늘도 푸는데 오래걸리지 않았다!

입력

사진에서도 볼 수 있듯이 int 배열 1개와 int 1개가 주어진다.

---

풀이 및 코드

주어진 하나의 int 숫자만큼 차이나는 쌍이 배열에 몇개 있는지 구하는 문제이다.

이 때 쌍은 중복되지 않아야한다.

오늘은 처음부터 정답을 생각해냈다.

먼저 배열을 정렬한다.

일단 각 원소의 개수를 저장하는 해쉬맵을 만들고 저장한다.

k가 0이라면 각 원소의 개수가 2 이상일 때 결과값에 1을 더한다. (이 때 각 원소는 중복되지 않게 탐색해야한다.)

k가 0이 아니라면 각 원소의 k를 더한 값이 해쉬 맵에 있는지 판단하고 있다면 결과값에 1을 더한다. (이 때 각 원소는 중복되지 않게 탐색해야한다.)

이런식으로 시간복잡도 O(NlogN)에 풀 수 있는 방법을 생각해냈다. (해쉬맵에 foreach 구문을 달면 O(N)으로 가능하지만 자바로는 문법이 귀찮아서 그냥 정렬을 하느라 O(NlogN)에 풀었다.)

이제 코드를 봐보자!

풀이코드

class Solution {
    public int findPairs(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        Arrays.sort(nums);
        // pre는 중복 원소를 피하기 위한 장치
        int result = 0, pre = -20000000;

        for(int i = 0; i < nums.length; i++)
        {
            if(!map.containsKey(nums[i]))
                map.put(nums[i], 0);

            map.put(nums[i], map.get(nums[i]) + 1);
        }

        if(k == 0)
        {
            for(int i = 0; i< nums.length; i++)
            {
                if(pre == nums[i])
                    continue;

                pre = nums[i];

                if(map.get(nums[i]) >= 2)
                    result++;
            }
        }
        else
        {   
            for(int i = 0; i < nums.length; i++)
            {
                if(pre == nums[i])
                    continue;

                pre = nums[i];

                if(map.containsKey(nums[i] + k))
                    result++;
            }
        }

        return result;
    }
}

---

제출 화면

오늘은 어렵지 않게 풀었던 문제였다.

하지만 해쉬맵에 foreach를 사용하는 생각은 아직도 바로바로 떠오르는 생각은 아니라서 좀 더 익숙해져야겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.