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

2022년 2월 03일 목요일 - 오늘도 뚠뚠 개미는 뚠뚠 열심히 일을 하네

오늘 올려볼 문제는 454번 4Sum II 이라는 문제이다.

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

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

으아 휴일이 끝나부러써

입력 예제

사진에서도 볼 수 있듯이 int 배열 4개를 입력받는다.

---

풀이 및 코드

4개의 배열에서 값 하나씩 뽑은 후 전부 합한 값이 0이 되는 경우의 수를 찾는 문제이다.

처음에는 for문 3개를 돌리고 나머지 하나의 값은 이진탐색으로 찾는 방법을 시도했었다.

하지만 O(N^3) 이상되는 시간복잡도 때문에 time limit exceeded가 났다.

그래서 다른 방법을 찾아보았다.

그래서 생각한 방법은 hashmap을 활용하는 것이다.

2중 for문을 2번 돌려 hashmap에 저장된 값을 활용하는 방식이다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int result = 0;

        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

        for(int i = 0; i < nums1.length; i++)
        {
            for(int j = 0; j < nums2.length; j++)
            {
                if(!map.containsKey(nums1[i] + nums2[j]))
                    map.put(nums1[i] + nums2[j], 0);
                map.put(nums1[i] + nums2[j], map.get(nums1[i] + nums2[j]) + 1);
            }
        }

        for(int i = 0; i < nums3.length; i++)
        {
            for(int j = 0; j < nums4.length; j++)
            {
                if(map.containsKey(-1 * (nums3[i] + nums4[j])))
                    result += map.get(-1 * (nums3[i] + nums4[j]));
            }
        }

        return result;
    }

}

---

제출 화면

오늘은 회사에서 오늘의 문제를 풀었다.

사실 오늘의 문제 존재를 회사를 다니면서 알았기에 사실은 오늘같은 날이 더 많을 것이다.

오늘 쉽게 푼 편은 아니라서 꽤 힘들었지만 그래도 풀긴 풀었다

내일도 문제를 풀어서 기분좋게 퇴근할 수 있으면 좋겠다.