문제) 배열의 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력해라
https://leetcode.com/problems/3sum/description/
풀이)
1.브루트 포스
먼저 브루트포스로 풀이했다. 이때 중복되는 값일 경우에는 무시하도록 continue 해주었다.
▶ [ -4 , -4 , 1 , 2 , ... , 1 ] 일 경우에 -4 다음에 다시 -4가 나오면서 결과가 중복되므로 이 경우에는 무시하고 넘어가도록 해준다는 의미이다.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = []
nums.sort()
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1] :
continue
for j in range(i + 1, len(nums) - 1):
if j > (i+1) and nums[j] ==nums[j-1] :
continue
for k in range(j + 1, len(nums)):
if k > (j+1) and nums[k] == nums[k-1] :
continue
if nums[i] + nums[j] + nums[k] == 0:
result.append([nums[i], nums[j], nums[k]])
return result
다만 이렇게 부르트포스로 풀게되면 Time Limit Exceeded를 맞이할 수 있다.
2. 투 포인터 접근
그렇다면 다른 방법을 생각해보자. 합을 0으로 만드는 인덱스가 아닌 값을 반환하므로 투 포인터를 사용할 수 있을 것이라 생각된다. 아래와 같은 원리로 생각하여 풀이를 했다.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = []
#오름차순 정렬
nums.sort()
for i in range(len(nums)-2) :
#중복된 값 건너뛰기
if i > 0 and nums[i] == nums[i-1] :
continue
#포인터 설정
left , right = i+1 , len(nums)-1
while left < right :
sum = nums[i] + nums[left] + nums[right]
#만일 sum이 0보다 클 경우 좌측으로 한 칸
if sum > 0 :
right -= 1
#만일 sum이 0보다 작을 경우 우측으로 한 칸
elif sum < 0 :
left += 1
#sum이 0일 경우 해당 값 append
else :
result.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
right -= 1
left += 1
return result
'코딩테스트 (Coding Test)' 카테고리의 다른 글
[LeetCode] - 주식을 사고팔기 가장 좋은 시점 (0) | 2023.11.14 |
---|---|
[LeetCode] - 배열 파티션 I (0) | 2023.11.14 |
[LeetCode] - 두 수의 합 (0) | 2023.11.14 |
[프로그래머스] Lv1 문제풀이 (1) | 2023.10.09 |
[프로그래머스] Lv1 문제풀이 (0) | 2023.10.09 |