[LeetCode] 15. 3sum (Medium) 2023/5/1

문제 제목	정답률	난이도
15. 3sum	32.6%	Medium

3Sum - LeetCode

 

문제요약

정수형 배열이 주어지면 합이 0이 되는 3개의 숫자쌍을 모두 반환하여라

조건 1) 원소가 3개 이상 1000개 이하인 정수형 배열이 주어지며 배열의 특정 요소는 3개의 숫자쌍에서 중복되지 않는다

조건 2) 3개의 숫자쌍의 순서는 신경 쓰지 않아도 된다

 

 

생각했던 풀이 1. Brute-Froce(모든 가능한 경우를 하나씩 대입) -> for 문장 세 개 사용해서 구하기 - (시간복잡도 $O(n^{3})$) 

생각했던 풀이 2. 배열을 정렬한 뒤, 투포인터 이용 -> sort(), for 사용해서 풀이 - (시간복잡도 $O(n^{2})$)

 

 

풀이 2-1 (1459 ms)

투포인터 이용

 

Step1. 배열을 정렬 -> sort() 함수

 

 

Step2. 첫 번째, 두 번째, 세 번째 원소값의 합을 기준으로 포인터 위치 변경 -> for, while

음수이면 왼쪽 포인터 위치 증가

0이면 세 원소를 결과에 추가

양수이면 오른쪽 포인터 위치 감소

 

 

Setp3. 중복된 원소 리스트에서 제거 -> set 함수 이용

 

리스트의 원소에 중복제거 하는 법_일차원 배열일 때 (단순 형변환)	list(set(list_value))
리스트의 원소에 중복제거 하는 법_이차원 이상의 배열일 때 (튜플 이용)	set(list(map(tuple, (list_value))))

 

 

구현 1 (4038ms)

모든 경우의 수를 구한 뒤, set의 특성(동일한 원소는 하나로 취급)을 이용해서 중복을 제거

최적화 Point

• 3개의 순서쌍 이므로 첫번째 원소의 인덱스는 0~len(nums)-3 까지 가능하다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result=[]
        for idx in range(0, len(nums)-2):
            first=nums[idx]
            left=idx+1
            right=len(nums)-1
            while(left<right):
                second=nums[left]
                third=nums[right]
                now_sum=first+second+third
                if now_sum<0:
                    left+=1
                elif now_sum>0:
                    right-=1
                else:
                    result.append([first, second, third])
                    left+=1
                    right-=1
        return set(list(map(tuple,(result))))

 

 

풀이 2-2 (1459 ms)

투포인터 이용

 

Step1. 배열을 정렬 -> sort() 함수

 

 

Step2. 첫 번째, 두 번째, 세 번째 원소값의 합을 기준으로 포인터 위치 변경 -> for, while

음수이면 왼쪽 포인터 위치 증가

0이면 세 원소를 결과에 추가

양수이면 오른쪽 포인터 위치 감소

 

 

Setp3. 중복된 원소 특별처리

첫 번째 원소 : 중복된 원소 n개이면 2개 남기는 위치에 선정 (중복된 원소 하나 전에서 시작)

두 번째, 세 번째 원소 : 중복된 원소가 나오면, 왼쪽 포인터는 증가시키고 오른쪽 포인터는 감소

(중복된 원소 3개인 경우 가능한 단 하나의 경우의 수인 (0, 0, 0)은 idx 반복문의 조건인 len(num)-2에 의해 제외되지 않는다)

 

 

구현 2 (1459ms)

모든 경우의 수를 구한 뒤, set의 특성(동일한 원소는 하나로 취급)을 이용해서 중복을 제거

최적화 Point

• 3개의 순서쌍 이므로 첫번째 원소의 인덱스는 0~len(nums)-3 까지 가능하다.
• 중복되는 원소가 들어오면 continue 구문을 사용해 코드를 실행하지 않게 한다
  • 단, 첫번째 원소는 중복된 원소 하나 전에서 시작하게 한다 ( -1, -1, 2) 이런 형식일 수도 있기 때문이다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result=[]
        for idx in range(0, len(nums)-2):
            if idx>0 and nums[idx-1]==nums[idx]:
                continue
            first=nums[idx]
            left=idx+1
            right=len(nums)-1
            while(left<right):
                second=nums[left]
                third=nums[right]
                now_sum=first+second+third
                if now_sum<0:
                    left+=1
                elif now_sum>0:
                    right-=1
                else:
                    result.append([first, second, third])
                    while left<right and second==nums[left+1]:
                        left+=1
                    while left<right and third==nums[right-1]:
                        right-=1
                    left+=1
                    right-=1
        return result

 

반복문 안에 또 반복문으로 조건 처리를 하기보다는, if-continue 구문을 이용하면 시간이 더 단축된다.