18. 4Sum

4Sum - LeetCode

정수 배열이 주어진다.

4개의 정수를 골라 합이 target이 되는 조합 목록을 반환하는 문제다.

단 고른 4개의 정수는 인덱스 값이 모두 달라야 하고, 조합 목록에 중복되는 조합은 제거 후 반환해야 한다.

 

접근법

pointer를 이용해 3 Sum 까지는 구해봤으니 4 Sum도 동일하게 구할 수 있을 것이다.

단 3 Sum은 1중 for문 안에서 pointer를 조작했으니 4 Sum은 2중 for문 안에서 pointer를 조작하면 되지 않을까?...

 

1. 2 pointer

from typing import *


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

        nums.sort()
        answer = set()
        for a in range(len(nums) - 2):
            for b in range(a + 1, len(nums) - 2):
                c, d = b + 1, len(nums) - 1

                while c < d:
                    cur = nums[a] + nums[b] + nums[c] + nums[d]

                    if cur == target:
                        answer.add(tuple([nums[a], nums[b], nums[c], nums[d]]))

                        while c < d and nums[c] == nums[c + 1]:
                            c += 1
                        while c < d and nums[d] == nums[d - 1]:
                            d -= 1
                        c, d = c + 1, d - 1
                    elif cur > target:
                        d -= 1
                    elif cur < target:
                        c += 1

        return list(map(lambda x: list(x), list(answer)))

접근법에 적혀있는 그대로 구현했다.

우선 2 pointer를 사용하기 적합하게 정렬을 해주었다.

여기서 중복된 조합을 구하지 않기 위해서 c와 d를 같은 값이면 추가로 전진시켜주었는데 여전히 중복된 값이 결과에 나와서 그냥 tuple로 받고 set으로 저장한 다음에 마지막에 list로 변환했다.

 

원인을 생각해보니 b와 a도 마찬가지로 중복 값이면 전진을 시켜줘야 하는데 2중 for문에 걸린 a, b는 c++이나 java처럼 for문 안에서 값을 변경한다고 반복문이 돌아가는 횟수가 변경되지 않는다. Python은 원래 그렇다.

 

2. 1번 개선

from typing import *


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

        nums.sort()
        answer = []
        a = 0
        while a < len(nums) - 3:
            b = a + 1
            while b < len(nums) - 2:
                c, d = b + 1, len(nums) - 1

                while c < d:
                    cur = nums[a] + nums[b] + nums[c] + nums[d]

                    if cur == target:
                        answer.append([nums[a], nums[b], nums[c], nums[d]])
                        while c < d and nums[c] == nums[c + 1]:
                            c += 1
                        while c < d and nums[d] == nums[d - 1]:
                            d -= 1
                        c, d = c + 1, d - 1
                    elif cur > target:
                        d -= 1
                    elif cur < target:
                        c += 1

                while b < len(nums) - 2 and nums[b] == nums[b + 1]:
                    b += 1
                if b > len(nums) - 2:
                    break
                b += 1
            while a < len(nums) - 3 and nums[a] == nums[a + 1]:
                a += 1
            if a > len(nums) - 3:
                break
            a += 1

        return answer

그럼 for문을 전부 while문으로 풀어준 뒤에 a, b도 전진 처리 로직을 넣어주면 된다.

코드가 예쁘진 않지만 아무튼 시간을 줄이긴 했다.

 

 

한 번에 풀어서 예전에 비슷한 걸 풀었었나 싶었더니 비슷한 걸 풀어서 한 번에 풀었나 보다;

454. 4Sum II