[리트코드(LeetCode)] 15. 3Sum - Python

leetcode.com/problems/3sum/

3Sum - LeetCode

- <파이썬 알고리즘 인터뷰>를 학습하면서 수록된 코드를 참고하였습니다. - 

 

풀이 1. 부르트 포스로 계산 -> 타임아웃 발생

for문을 3번 사용해서 풀이하는 단순한 방법으로 O(n^3)의 시간복잡도를 가지는 방법이다.

for 문을 들어가서 해당 인덱스가 가리키는 리스트의 값이 바로 이전 원소 값과 동일하다면 continue 시켜줘서 중복을 제거한다.

리트코드에서 이 방법은 타임아웃을 발생시킨다.

class Solution:
    # 풀이 1. 부르트 포스 -> 타임 아웃
    def threeSum_bruteforce(self, nums: List[int]) -> List[List[int]]:
        results = []
        nums.sort()  # O(nlogn)

        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            for j in range(i + 1, len(nums) - 1):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue

                for k in range(j + 1, len(nums)):
                    if k > j + 1 and nums[k] == nums[k - 1]:
                        continue

                    if nums[i] + nums[j] + nums[k] == 0:
                        results.append([nums[i], nums[j], nums[k]])

        return results

 

 

풀이 2. 투포인터로 합 계산

for 문으로 앞에서부터 차례로 값을 선택하고 해당 값 이후에 리스트들에 대해 투포인터를 적용하여 풀이한다.

sum = for문으로 선택된 값 + left번째의 값 + right번째 값 이라고 한다면

sum > 0 이면 right -= 1

sum < 0 이면 left += 1

sum == 0 이면 results에 추가한다.

class Solution:
	def threeSum(self, nums: List[int]) -> List[List[int]]:
        results = []
        nums.sort()

        for i in range(len(nums) - 2):
            left, right = i + 1, len(nums) - 1

            if i > 0 and nums[i] == nums[i - 1]:
                continue

            while left < right:
                sum = nums[i] + nums[left] + nums[right]

                if sum > 0:
                    right -= 1
                elif sum < 0:
                    left += 1
                else:
                    results.append([nums[i], nums[left], nums[right]])

                    # 중복 제거
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1

                    left += 1
                    right -= 1

        return results

 

www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9791189909178

파이썬 알고리즘 인터뷰 - 교보문고