Leetcode 3 sum 문제

https://leetcode.com/problems/3sum

input 조건은 아래와 같다.

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

배열 내의 세 숫자의 합이 0이 되는 경우, 중복되지 않게 그 숫자들을 리스트에 담아 반환하는 문제이다.

input 배열의 크기가 최대 3000이므로 반복문이나 재귀를 통해 완전탐색을 진행할 경우 O($n^3$)으로 시간초과가 날 수 있다.

따라서 O($n^2logn$) 이내로 해결해야 하는데, 이에 대한 열쇠가 정렬이라고 생각하였다.

Example 1의 경우를 예시로 들어보자.

input 배열이 [-1, 0, 1, 2, -1, -4]인데 이를 정렬하면 [-4, -1, -1, 0, 1, 2]가 된다.

-4	-1	-1	0	1	2
start	mid				end

오름차순이라는 강점을 이용하기 위해 start, mid, end라는 3가지 인덱스 포인터를 이용하였다.

start를 0부터 size - 2까지 이동시키며, 각 start마다 start mid end의 합을 고려해 mid와 end를 이동시킬 것이다.

-4	-1	-1	0	1	2
start	mid				end

현재 start + mid + end의 값은 -3으로 음수이다. 따라서 mid를 오른쪽으로 한 칸 이동시켜 값을 키우고 합이 0이 나오도록 유도한다.

-4	-1	-1	0	1	2
start		mid			end

현재 start + mid + end의 값은 여전히 -3으로 음수이다. mid를 오른쪽으로 이동시키자.

-4	-1	-1	0	1	2
start			mid		end

현재 start + mid + end의 값은 -2로 여전히 음수이다. mid를 이동시킨다.

-4	-1	-1	0	1	2
start				mid	end

현재 start + mid + end의 값은 -1로 음수이다. 하지만 mid를 더 이동시킬 수 없으므로 start를 1 증가시키고 다음 반복문을 실행한다.

-4	-1	-1	0	1	2
	start	mid			end

현재 start + mid + end의 값은 0으로 조건을 만족한다. 따라서 세 숫자를 리스트에 추가하고 mid를 증가시켜 탐색을 계속한다.

-4	-1	-1	0	1	2
	start		mid		end

현재 start + mid + end의 값은 1로 양수이다. 따라서 end를 왼쪽으로 이동시킨다.

-4	-1	-1	0	1	2
	start		mid	end

현재 start + mid + end의 값은 0으로 조건을 만족한다. 따라서 세 숫자를 리스트에 추가하고 진행한다.

위 로직을 반복해서 진행하며 결과를 탐색한다.

start를 0~size-2까지 이동시키는 동안 mid와 end를 조정하며 start+1부터 end까지 탐색하므로 O($n^2$)의 시간복잡도를 갖는다.

하지만 주의해야 할 점이 있다.

위의 예시를 진행하는 도중 찾은 합이 0이되는 케이스가 중복될 수 있다는 점을 아직 처리하지 않았다.

나는 이 중복 케이스에 대한 처리를 Map으로 구현하였다.

포인터 작업을 통해 합이 0이 되는 start mid end값을 찾으면, 이를 리스트로 결과 배열에 추가하기 전에 작업을 한다.

리스트의 toString()메소드를 사용할 경우 [-1, -1, 2]처럼 배열의 원소들에 대한 문자열이 등장하는데, 이를 Map의 key로 사용하여 중복검사를 진행하였다.

로직 상 start < mid < end를 항상 만족하므로 사용할 수 있는 방법이다.

class Solution {
    fun threeSum(nums: IntArray): List<List<Int>> {
        val sortedNums = nums.sorted()
        val overlap = TreeMap<String, Boolean>()
        val answer = mutableListOf<List<Int>>()

        for(start in 0 until sortedNums.size - 2){
            var mid = start + 1
            var end = sortedNums.size - 1

            while(mid < end){
                val sum = sortedNums[start] + sortedNums[mid] + sortedNums[end]

                if(sum > 0) end--
                else if(sum < 0) mid++
                else{
                    val case = listOf(sortedNums[start],sortedNums[mid],sortedNums[end])
                    if(overlap[case.toString()] == null){
                        answer.add(case)
                        overlap[case.toString()] = true
                    }
                    mid++
                }
            }
        }

        return answer
    }
}

중복 검사를 위한 Map을 사용할 때 처음핸 mutableMapOf()를 사용하여 진행하였으나, 속도와 메모리 면에서 꽤나 느려 레드블랙트리 기반의 TreeMap을 사용하였더니 훨씬 가볍고 빨라졌다.

용량 부분의 감소량은 Map 구현 방법에 기반해 예상해볼 수 있으나 속도가 왜 빨라졌는지는 아직 잘 모르겠어서 공부해 볼 예정이다.