LeetCode 18(4Sum, Python)

1. 문제 링크

• https://leetcode.com/problems/4sum/description/

4Sum - LeetCode

2. 문제 설명

• 정수로 구성된 nums라는 array가 주어졌을 때, 
  • nums[a] + nums[b] + nums[c] + nums[d] == target이 되는 unique한 모든 조합을 반환
• 예시) nums = [1,0,-1,0,-2,2], target = 0일 때, 네 수의 합이 0이 되는 [[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]]을 반환 

3. 처음 풀이 

• 지난번에 풀었던 3Sum 방법(two pointer, sorting)을 응용 
  • 3Sum에서는 첫번째 index에 대해 for문을 돌리고, left end index를 two pointer로 조정했다면, 
  • 4Sum은 첫번째, 두번째 index에 대해 for문을 돌리고, third, end index를 two pointer로 조정하는 것으로 수정 
    
    • 변수명이 길어져서, 첫번째, 두번째는 i,j로 두고, third, end index는 left, right로 변수화
    • left, right는 현재의 sum과 target sum을 비교하면서, 같으면 append,
    • 현재 sum이 더 크면 작아지는 방향으로 (right를 좌로 한칸 이동)
    • 현재 sum이 더 작으면 커지는 방향으로 (left를 우로 한칸 이동) 움직이면서 left < right 동안 while문 수행
  • 같은 output이 나오는 케이스를 제거해줘야 runtime이 조금 더 올라갔음

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        output = []

        for i in range(len(nums)-3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue  # 중복된 값을 건너뛰기

            for j in range(1, len(nums)-2):
                if j > i+1 and nums[j] == nums[j-1]:
                    continue # 중복된 값을 건너뛰기 
                if j > i: 

                    left =  j+1
                    right = len(nums) -1 
                    cur_target = target -nums[i] - nums[j]

                    while left < right:
                        if nums[left] + nums[right]==cur_target:
                            output.append([nums[i], nums[j], 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
        
                        elif nums[left] + nums[right] < cur_target:
                            left +=1
                        else:
                            right -=1

        return output

• runtime 65% beats 
• 신기했던건, cur_sum = nums[i]+nums[j]+nums[left]+nums[right] 으로 놓고, cur_sum과 target을 비교하는 방식으로 코드를 짰을 땐, runtime 이 45% 정도 beats이었음. 
  • nums가 엄청 커졌을 때, 특정 index의 값을 반환하는 게 시간이 소요되서 그런듯 함 

4. 다른 풀이

• 대부분이, 내가 접근한 방식으로 풀었음. 
• 거의 비슷한데 두가지 정도 속도 개선 포인트가 존재했음 
  • 우선 나는 output 을 빈 list로 두었는데, 여기선 set()으로 빈 집합으로 두고, 반환 시에만 list로 변경해주었음
    • set으로 두면 set.add했을 때 이미 있는 값이라면, 중복되서 add되지 않고 고유한 한개의 값으로 존재하기 때문에, 자동으로 중복이 제거됨 
  • break rule이 하나 더 추가 되어있음
    • 만약 nums[i] > target/4 면 break하는 조건을 추가 
      • nums는 오름차순으로 sorting이 되어있는데, start index를 4배한 것이 이미 target보다 커버리면, for문을 계속 돌릴 이유가 없어져서 break를 걸면 불필요한 while문이 안돌게 됨!
  • 이 풀이로 submission을 하면 runtime 기준 35% 정도 개선이 되고, 82.79% beats!

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = set()
        for i in range(len(nums) - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            if nums[i] > target / 4:
                break
            for j in range(i + 1, len(nums) - 2):
                l, r = j + 1, len(nums) - 1
                while l < r:
                    sm = nums[i] + nums[j] + nums[l] + nums[r]
                    if sm < target: l += 1
                    elif sm > target: r -= 1
                    elif (nums[i], nums[j], nums[l], nums[r]) not in res:
                        res.add((nums[i], nums[j], nums[l], nums[r]))
                    else: l, r = l + 1, r - 1
        return [list(t) for t in res]

 

5. 배운 점

• 핵심을 파악해서 풀 되, 불필요한 for문 while문이 도는 케이스가 있는지 파악해서 runtime 개선하기!