LeetCode발행일 2025. 3. 13.원본 https://blog.naver.com/jword_/223794009727 ↗

투 포인터 응용하기 2 - 4Sum

투 포인터 응용하기 2 - 4Sum — #LeetCode #개발자의도구들 #투포인터 #4Sum only 파이썬 목표 참고 : 여기 전략 생각하기 해당 문제를 ...

#LeetCode#Naver Blog

#LeetCode #개발자의도구들 #투포인터 #4Sum

only 파이썬
목표 참고 : 여기

전략 생각하기
LeetCode(medium 18. 4 Sum)

해당 문제를 풀기전에 바로 이전문제는 3 Sum이었다. 꽤나 오랜시간이 걸려서 문제를 해결했다. 기억이 쌩쌩한김에 바로 다음 문제에 도전하고자 한다.

javascript 코드 예제

                                    ⚠️ 입력값: 1~200
>>> 🤔 O(n³)도 될 것 같은데?

✅ 3Sum에서 밖에 for루프를 하나 더 추가해서 구현해보자
>>> O(n³)으로

javascript 코드 예제

                                    class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """

        result = []
        nums.sort()
        print("nums(sorted)", nums)

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

                while start < end:
                    tmp += nums[start] + nums[end]
                    print("tmp", tmp)

                    if tmp > target - boundary:
                        end -= 1
                    elif tmp < target - boundary:
                        start += 1
                    elif tmp == target - boundary:
                        print("[result]", [nums[i], nums[j], nums[start], nums[end]])
                        print("tmp: ", tmp)

                        result.append([nums[i], nums[j], nums[start], nums[end]])

                        while start < end and nums[start] == nums[start + 1]:
                            start += 1
                        while start < end and nums[end] == nums[end - 1]:
                            end -= 1

                        start += 1
                        end -= 1

        return result

오답이다.
밖 포인터가 하나더 있어서 3Sum을 변형시켜줘야 한다.
어디선가 로직이 잘못되었다

javascript 코드 예제

                                     while start < end:
    print("<<<test>>>")
    print("j, start, end", nums[j], nums[start], nums[end], "for target-boundary", target-boundary )
    tmp = nums[j] + nums[start] + nums[end]
    print("tmp test", tmp)

tmp값을 매번 새롭게 갱신하지 않아서 문제가 발생했던 것이다.

정답코드

javascript 코드 예제

                                    class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """

        result = []
        nums.sort()

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

                while start < end:
                    tmp = nums[j] + nums[start] + nums[end]

                    if tmp > target - boundary:
                        end -= 1
                    elif tmp < target - boundary:
                        start += 1
                    elif tmp == target - boundary:

                        result.append([nums[i], nums[j], nums[start], nums[end]])

                        while start < end and nums[start] == nums[start + 1]:
                            start += 1
                        while start < end and nums[end] == nums[end - 1]:
                            end -= 1

                        start += 1
                        end -= 1

        return result

정답이다.
예상대로 t-O(n³)임에도 정답이다.
t: O(n³) 86.22% Beats

포인터가 추가됨에 따라 디테일하게 로직이 조금씩 바뀌는 것을 잘 캐치하는 것이 중요해보인다.