[LeetCode 해석 및 풀이] 15. 3Sum

LeetCode 문제 해석 및 풀이 방법

 

문제 15. 3Sum(3개의 합)

바로가기

 

문제 설명

영문

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

 

한글

정수 배열 nums가 주어지면, i,j,k가 서로 다르고, nums[i] + nums[j] + nums[k] == 0가 되는 모든 트리플 [nums[i], nums[j], nums[k]]을 반환하세요.

 

답에는 반드시 중복된 트리플이 포함되지 않도록 주의하세요.

 

제한조건

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

 

입출력 예

입력	출력
[-1,0,1,2,-1,-4]	[[-1,-1,2],[-1,0,1]]
[0,1,1]	[]
[0,0,0]	[[0,0,0]]

 

 

해답 및 해설

파이썬 (Python)

숫자 하나를 정해두면 Two Sum 문제와 같아지는 문제.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        count = defaultdict(int)
        for n in nums:
            count[n] += 1
        
        answer = []

        # 셋 다 0 인경우
        if 0 in count and count[0] >= 3:
            answer.append([0,0,0])
        
        # 2개 중복, 1개는 다른 경우
        for n in count:
            if n == 0: continue
            if -2*n in count and count[n] >= 2:
                answer.append([n, n, -2*n])
        
        # 셋 다 다른 경우
        num_list = sorted(count.keys())
        length = len(num_list)

        for i in range(length):
            if num_list[i] > 0: break
            for j in range(i+1, length):
                target = -num_list[i] - num_list[j]
                if target <= num_list[j]: break
                if target in count:
                    answer.append([num_list[i], num_list[j], target])
        
        return answer

 

우선 트리플 안에 숫자가 중복되서 들어가는 경우를 먼저 체크해주고, 이후 셋 다 다른 숫자인 경우를 체크해주었다.

셋 다 다른 경우를 체크할 때는 시간복잡도가 O(a^2) (a는 숫자의 가짓수)이므로 정렬(O(aloga))해주어도 시간상의 손해가 없었고, 정렬 후 계산하면 맞지 않은 경우를 사전에 거를 수 있어서 이득이었다.