[Python] 3Sum

Medium 난이도 Acceptence 28.4 문제

 

입력 리스트에서 3개의 원소를 더해 0이 되는 subarray를 구하는 문제, 순서만 다른 subarray는 허용되지 않는다.

 

처음에 3중 반복문으로 풀려고 했지만 성능이 매우 좋지않아 TimeLimitError가 발생한다, 따라서 최대 2중 반복문 이하의 시간복잡도를 가지도록 풀어야 한다.

 

우선 입력값을 정렬하였고, 첫 원소부터 마지막 첫번째가 되는 원소까지 반복한다.

루프 시작에 이전 원소와 같아 검사할 필요가 없거나 최소값에 최댓값 2개를 더햇을 경우에도 0이 되지않는 경우를 미리 검사해 필요없는 계산을 하지 않도록 한다.

 

그리고 0이되는 값을 검사할 땐 quick sort의 값을 찾는 개념으로 왼쪽 pivot과 오른쪽 pivot을 정해 값의 크기를 이용해 0이되는 값을 찾는다.

 

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        output, temp, length = [], [], len(nums)
        if length < 3:
            return output
        
        nums.sort()
        for i in range(0, length-2):
            if ((i > 0 and nums[i] == nums[i-1]) or sum([nums[i]]+nums[-2:]) < 0):
                continue

            left, right = i+1, length-1
            while left < right:
                tempList = [nums[i], nums[left], nums[right]]
                tempSum = sum(tempList)
                if tempSum > 0:
                    right -= 1
                elif tempSum < 0:
                    left += 1
                else:
                    output.append(tempList)
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
                    while left < right and nums[right] == nums[right+1]:
                        right -= 1

        #output = list(set([tuple(item) for item in output])) 2차원 리스트 중복제거, tuple(set(item)) 하면 모든 요소 제거
        return output