15. 3Sum

1. my code

trash 같이 풀었음. 간단하게 풀려고 노력한게 더 복잡하게 풀게 된 결과.. 공간복잡도 + 시간복잡도 매우 좋지 않음. 

일단 내 생각으로는 각 수의 절대값으로 Map을 만들어주고 각 값의 부호에 따라 양수면 Pair의 first++, 음수면 second++을 해줌. 그리고 그 맵의 키 값으로 정렬을 해줌. answer에 추가해주는 조건은 (a, b, c) 모두 다 다른 값이면 같은 부호인 값에 대해서는 b < c를 해줌. 

1. 키 중 0이 있다면 맵 중에서 value의 first, second 둘 다 0이 아닌 값에 한해서 answer에 추가

2. 맵에서 음수인 값이 존재하는 맵들에 대해서만 음+양+양 조합 찾음. 먼저 음수절대값 / 2가 떨어지면 음수절대값 / 2한 값의 개수가 2개 이상이면 추가. 그것이 아닐 때 -> 음수가 가장 커야되므로 음-양 >0 에 대해서만 적용. [음-양]이 키로 되는 값의 first(양수의 개수)가 존재하면 answer에 추가. 

3. 양, 양, 음 조합을 찾기 위해 2번 알고리즘 또 사용

import kotlin.math.*
class Solution {
    fun threeSum(nums: IntArray): List<List<Int>> {
        val map = mutableMapOf<Int, Pair<Int, Int>>()
        nums.map {
            val absNum = abs(it)
            val (positiveCount, negativeCount) = map.getOrDefault(absNum, Pair(0, 0))
            if (it > 0) {
                map[absNum] = Pair(positiveCount + 1, negativeCount)
            } else if (it < 0) {
                map[absNum] = Pair(positiveCount, negativeCount + 1)
            } else {
                map[absNum] = Pair(positiveCount + 1, negativeCount)
            }
        }
        val answer = mutableSetOf<List<Int>>()
        map.toSortedMap()
        if ((map[0]?.first ?: 0) > 0) {
            val tmp = map.filter {
                it.value.first > 0 && it.value.second > 0
            }
            tmp.map {
                answer.add(listOf(it.key * -1, 0, it.key))
            }
            if ((map[0]?.first ?: 0) >= 3) {
                answer.add(listOf(0, 0, 0))
            }
            
            map.remove(0)
        }
        val minus = map.filter { it.value.second > 0 }
        val plus = map.filter { it.value.first > 0 }
        minus.forEach { (key, _) ->
            if (key % 2 == 0 && (map[key / 2]?.first ?: 0) >= 2) {
                answer.add(listOf(key * -1, key / 2, key / 2))
            }
            plus.map { (plusKey, _) ->
                if (plusKey >= key) {
                    return@map
                }
                if (plusKey * 2 != key && (map[key - plusKey]?.first ?: 0) > 0) {
                    answer.add(listOf(key * -1, min(plusKey, key - plusKey), max(plusKey, key - plusKey)))
                }
            }
        }
        plus.forEach { (key, _) ->
            if (key % 2 == 0 && (map[key / 2]?.second ?: 0) >= 2) {
                answer.add(listOf(key, -key / 2, -key / 2))
            }
            minus.map { (minusKey, _) ->
                if (minusKey >= key) {
                    return@map
                }
                if (minusKey * 2 != key && (map[key - minusKey]?.second ?: 0) > 0) {
                    answer.add(listOf(key, min(-minusKey, -key + minusKey), max(-minusKey, -key + minusKey)))
                }
            }
        }
        return answer.toList()
    }
}

 

2. others' code

괜히 꼬아서 생각한 것 같음. 일단 정렬을 해주고 첫 번째 원소부터 자기 자신 앞의 원소들에 한해서 자기자신 + 자기자신 앞의 두 원소의 합 = 0 이 되는 조합을 찾는게 맞았음. 이러면 중복 제거를 위해 set을 사용할 필요도 없었음. 

조건은 다음과 같음. 

1. 음수는 무조건 하나 이상 있어야 하니 기준점이 양수가 되는 순간 멈추기
2. 중복은 필요 없으니 이전 값과 현재 값이 같다면 continue
3. 나머지에 대해서 전체 탐색을 해주면 됨. 단 값에 따라서 더 큰 값이 필요하면 start++, 더 작은 값이 필요하면 end--를 해주면 됨. 
4. 계속 찾다가 start == end가 같아지는 순간이 오면 멈추고 다음 원소에 대해 1번부터 다시 실행. 

class Solution {
    fun threeSum(nums: IntArray): List<List<Int>> {
       nums.sort()
       val res = mutableListOf<List<Int>>( )
       for (i in 0 until nums.size) {
           if (nums[i] > 0) break
           if (i > 0 && nums[i - 1] == nums[i]) continue
           var start = i + 1
           var end = nums.size - 1
           while (start < end) {
               val sum = nums[start] + nums[end] + nums[i]
               if (sum < 0) {
                   start++
               } else if (sum > 0) {
                   end--
               } else {
                   res.add(listOf(nums[i], nums[start], nums[end]))
                   start++
                   end--
                   while (start < end && nums[start] == nums[start - 1]) {
                       start++
                   }
               }
           }
       }
       return res.toList()
    }
}