Algorithm Problem with Python — 34day
문제 설명 📖
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.
정수 배열 번호가 주어지면 i!= j, i!= k, j!= k와 같은 세 쌍둥이 [nums], nums[j], nums[j] + nums[k] == 0을 모두 반환합니다.
솔루션 세트에 중복된 세 쌍둥이를 포함해서는 안 됩니다.
제한사항⁵
- 0 <= nums.length <= 3000
- -10⁵ <= nums[i] <= 10⁵
입출력 예
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = []
Output: []
Example 3:
Input: nums = [0]
Output: []
문제 이해 🔑
이풋 배열에서 합으로 0을 만들 수 있는 3개의 인자를 출력하는 문제입니다.
이는 브루투 포스(brute force)로 계산하면 답은 얻어낼 수 있겠지만 3개의 인자를 더하는 과정을 만들기 위해 삼중 for문을 만들어 O(n³) 정도의 시간 복잡도가 예상됩니다.
그러므로 조금 더 효율적인 방법을 고민해야 합니다.
투 포인터로 합 계산하는 방식을 사용한다면 O(n²) 이내로 최적화가 가능할 겁니다.
정렬된 상태로 가정한다면 예시 1번은 [-4, -1, -1, 0, 1, 2]의 값을 가지게 됩니다.
3개 인자의 합이니까 첫 번째 인자는 nums[i], 두 번째 인자는 i를 기준으로 left는 i + 1, right는 배열 마지막 인자로 둡니다.
그리고 i + left + right를 더하면서 간격을 좁혀가며 계산하면 됩니다.
수도 코드 ✍️
-
인풋 배열을 정렬합니다.(추후에 left, right의 간격을 좁혀갈 때 3개의 인자의 합이 0보다 작으면 left의 값을 키워야 하고, 합이 0보다 크면 right의 값을 키워야 한다는 점을 예측할 수 있습니다.)
-
반복문을 통해 배열을 순회합니다.
이 때, i가 최댓값일 때 left, right가 존재하기 위해서 -2의 범위를 지정합니다. -
중복된 값을 건너뛰기 위해 조건문과 continue를 사용합니다.
예시 1번 정렬 상태([-4, -1, -1, 0, 1, 2])에서 1번 째 인자 -1가 i일 때 값이랑 2번 째 인자 -1이 i일 때 값이 동일합니다.
그래서 i가 0보다 크고 i와 i-1의 값이 동일할 땐 continue를 통해 아래 코드들이 진행되지 않고 넘어가도록 합니다. -
left, right는 i 기준으로 i+1, 배열 맨 마지막 값으로 지정합니다.
-
오름차순으로 정렬이 되었으니 right가 크다는 조건문을 작성하고 3개 인자의 합이 0보다 크면 right을 이동하고, 0보다 작으면 left를 이동하면서 간격을 줄입니다.
-
sum이 0이 나왔다면 left, right 양 옆으로 동일한 값이 있는지 확인하여 스킵할 수 있도록 처리합니다.
-
마지막으로 left를 우측, right를 좌측으로 이동하고 위의 로직을 반복합니다.
-
모든 반복문이 끝나면 sum이 0인 조합을 넣어두었던 배열을 리턴합니다.
코드 작성 ⌨️
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
results = []
nums.sort()
# i가 최대 값일 때 left, right가 존재하기 위해서 -2
for i in range(len(nums) - 2):
# 중복된 값 건너뛰기
if i > 0 and nums[i] == nums[i - 1]:
continue
# 간격을 좁혀가며 합 sum 계산
left, right = i + 1, len(nums) - 1
while left < right:
sum = nums[i] + nums[left] + nums[right]
if sum < 0:
left += 1
elif sum > 0:
right -= 1
else:
# sum = 0인 경우이므로 정답 및 스킵 처리
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정리 😄
바로 지난 문제와 비슷한 방식의 풀이를 사용했습니다.
투 포인터를 사용한 점과 기준을 잡고 범위를 줄여나가는 방식이였습니다.
이 문제에서는 브루트 포스로 계산하면 답은 구하나 시간 복잡도로 인해 타임아웃이 발생합니다.
그러므로 알고리즘을 풀 때 답만 구하기 보다 이처럼 효율적인 방법을 고민하는 것이 중요하다는 것을 또 한 번 느꼈습니다.
투 포인터의 풀이 방식은 많이 그리고 유용하게 쓰이기 때문에 따로 정리하는 시간을 갖도록 하겠습니다.
Reference
- 박상길, 『파이썬 알고리즘 인터뷰, 책만 (2020), p184-189.
