leetcode 15. 3Sum 풀이

문제 : 수열 nums 가 주어질때 3개의 원소를 더했을때 0 이 되는 부분 수열을 모두 반환하라. 단 중복되는 것은 하나만 반환한다.

Follow up : 문제는 어떻게든 풀었지만 시간과 메모리 사용량이 너무 많다. 다른 좋은 방법이 있을 것으로 예상된다.

 

아이디어 : 문제에 주어진 수열을 음수와 양수를 나누어서 각각 정렬된 list를 만든다. 경우의 수가 모두 3가지로

1. 0 으로만 이루어진 return

2. 음수에서 2개를 뽑고 양수에서 하나를 뽑는 경우

3. 양수에서 2개를 뽑고 음수에서 하나를 뽑는 경우

 

이러한 경우를 만든 후, timeout을 방지하기 위해 2개를 뽑아 더한 수의 절대값이 다른 list의 절대값이 가장 큰 원소를 넘는 경우, continue 했다.

 

코드 :

내가 작성한 코드

class Solution:
    ans = []
    def bs(s_list: List[int], value: int):
        s = 0
        e = len(s_list) - 1
        m = (s + e) // 2
        while s <= e:
            if s_list[m] == value:
                return True
            elif s_list[m] < value:
                s = m + 1
            else:
                e = m - 1
            m = (s + e) // 2
        return False
    def sol(s_list: List[int], t_list: List[int], negative):
        if not t_list:
            return
        if not s_list:
            return
        for idx1 in range(len(s_list)-1):
            for idx2 in range(idx1+1, len(s_list)):
                v = abs(s_list[idx1] + s_list[idx2])
                if negative == True:
                    vi = (-1) * v
                    if vi < t_list[0]:
                        continue
                else:
                    vi = v
                    if t_list[-1] < vi:
                        continue
                if Solution.bs(t_list, vi) == True:
                    a = sorted([s_list[idx1], s_list[idx2], vi])
                    if not a in Solution.ans:
                        Solution.ans.append(a)
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        Solution.ans = []
        neg = []
        pos = []
        d = {}
        if len(nums) < 3:
            return Solution.ans
        for num in nums:
            if not num in d:
                d[num] = 1
            else:
                d[num] += 1
        nums = sorted(nums)
        for num in nums:
            if num < 0:
                neg.append(num)
            else:
                pos.append(num)
        if 1 < len(neg):
            Solution.sol(neg, pos, False)
        if 1 < len(pos):
            Solution.sol(pos, neg, True)
        if 0 in d:
            if 2 < d[0]:
                Solution.ans.append([0,0,0])
                return Solution.ans
        return Solution.ans
            
            

다른 사람이 작성한 코드

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        N, result = len(nums), []
        for i in range(N):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            target = nums[i]*-1
            s,e = i+1, N-1
            while s<e:
                if nums[s]+nums[e] == target:
                    result.append([nums[i], nums[s], nums[e]])
                    s = s+1
                    while s<e and nums[s] == nums[s-1]:
                        s = s+1
                elif nums[s] + nums[e] < target:
                    s = s+1
                else:
                    e = e-1
        return result

 

학습 포인트 : 다른 사람의 코드를 보면 two pointer를 이용하여 불필요한 메모리 사용 및 시간 복잡도를 사용하지 않았다. two pointer에 대한 이해를 높이고, 코드를 완성한 후 최적화에 대한 고민을 조금 더 해보면 좋겠다.

 

출처 : leetcode.com/problems/3sum/