[LeetCode] 18. 4Sum (Kotlin)

1. 문제 소개

4Sum - LeetCode

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

 

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]]

 

Constraints:

• 1 <= nums.length <= 200
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

---

2. 문제 풀이

 2.1 Description 분석(요약)

1) 주어진 배열에서 4개의 숫자를 꺼낸 값들의 합이 target과 같은 쌍들을 리턴하는 문제이다.

2) 리턴하는 숫자의 쌍은 unique하며, 4개의 숫자들은 모두 distinct하다.

3) 주어진 배열의 사이즈가 4보다 작을 수 있으므로 예외처리가 필요하다.

 

---

 2.2 Approach

모든 유니크한 쌍의 합들을 구하는 방식밖에 생각나지 않았다.

이를 위해서는 처음부터(차례대로) 2개의 원소를 pivot 역할 하도록 loop를 돌려주며,

나머지에 대해선 포인터를 이용하여 만족하는 값들을 찾아주도록 하겠다.

 

계산하기 전 배열을 정렬한다. 정렬 한다면,

 1) 중복된 값을 골라낼 수 있다. (for-loop continue)

 2) 원하는 값(target) 보다 커질 경우 루프에서 탈출할 수 있다. (for-loop break)

 

---

 2.3 Algorithm

1) 주어진 배열의 크기를 확인하여 4개 보다 작을 경우 빈 리스트를 return한다.

 

2) 배열을 정렬한다. (Arrays.sort() or Collections.sort())

 

3) 만족하는 쌍을 저장할 리스트를 생성한다.

 

4) for-loop

     4-1) 첫 pivot 값의 4배가 원하는 값(target)보다 클 경우 break

     4-2) 첫 pivot 값이 중복될 경우 continue

 

     4-3) 두 번째 pivot의 for-loop

              4-3-1) 첫 번째 pivot 값과 두 번째 pivot 값 * 3의 합이 원하는 값보다 클 경우 break

              4-3-2) 두 번째 pivot 값이 중복될 경우 continue

 

              4-3-3) low pointer와 high pointer를 서로 교차할 때까지의 while 문

                         4-3-3-1) 모든 값의 합이 원하는 값(target)과 같을 경우 리스트에 값 추가

                         4-3-3-2) 포인터를 이동하되 값이 중복될 경우는 계속 지나감

                         4-3-3-3) 모든 값의 합보다 작을 경우 low pointer를 큰 쪽으로 이동

                         4-3-3-4) 모든 값의 합보다 클 경우 high pointer를 작은 쪽으로 이동

---

3. Code

class Solution {
    fun fourSum(nums: IntArray, target: Int): List<List<Int>> {

        if (nums.size < 4) return listOf() // (1)

        nums.sort() // (2)

        val sumList = arrayListOf<List<Int>>() // (3)
        for (i in 0..nums.size - 4) { // (4)
            if (nums[i] * 4 > target) break // (4-1)

            if (i > 0 && nums[i] == nums[i - 1]) continue // (4-2)

            for (j in (i + 1)..nums.size - 3) { // (4-3)
                if (nums[j] + nums[i] * 3 > target) break // (4-3-1)
                if (j > i + 1 && nums[j] == nums[j - 1]) continue // (4-3-2)

                var low = j + 1
                var high = nums.size - 1
                val forTarget = target - nums[i] - nums[j] // 계산 편의를 위함

                while (low < high) { // (4-3-3)
                    if (nums[low] + nums[high] == forTarget) {
                        sumList.add(listOf(nums[i], nums[j], nums[low], nums[high])) // (4-3-3-1)
                        // (4-3-3-2)
                        low++
                        while (low < high && nums[low] == nums[low - 1]) {
                            low++
                        }
                        high--
                        while (low < high && nums[high] == nums[high + 1]) {
                            high--
                        }
                    } else if (forTarget > nums[low] + nums[high]) { // (4-3-3-3)
                        low++
                    } else { // (4-3-3-4)
                        high--
                    }
                }
            }
        }

        return sumList
    }
}

 

---

4. 마치며

솔루션으로는 두 가지의 방식을 제공하였다. Two-Pointers 방식과 HashSet 방식이다.

또한, Recursion function으로 풀이하였으며, 두 개의 합(Two Sum) 방식을 이용하여 kSum으로 일반화할 수도 있었다.

 

HashSet을 이용한 Two Sum 문제는 상당히 쉽고 간단한 코드 작성으로 풀린다. 문제

A + B 합이 원하는 값이 같아야하므로   " A + B = target "  ▶  " A = target - B "   가 성립한다.

Two Sum 문제에서는 정확한 index 값을 반환해야하므로 HashSet이 아닌 HashMap을 이용하여 풀이하였다.
(HashSet과 HashMap의 차이는..)

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = HashMap<Int, Int>() // or hashMapOf<Int, Int>()
        for (i in nums.indices) {
            if (map.containsKey(target - nums[i])) {
                return intArrayOf(map[target - nums[i]]!!, i)
            }
            map[nums[i]] = i
        }
        return intArrayOf()
    }
}