미소를뿌리는감자의 코딩
[leetcode 2024/02/05] 15. 3Sum 본문
https://leetcode.com/problems/3sum/description/
1. 접근 방법
처음에 접근 했던 방법은 nums를 양수 list와 음수list로 나눈 후, 양수의 2개 값의 합의 *-1 이 음수에 있는지 였다.
이를 음수의 2개 값의 합의 * -1 이 양수에도 있는지 알아보았다.
하지만, 이 방법은 잘 풀리다가 뒤쪽 test code에서 runtime error가 났다.
다음을 runtime error가 난 코드이다.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
zeros = 0
total = set()
minus = []
plus = []
for i in nums:
if i == 0:
minus.append(i)
plus.append(i)
zeros +=1
elif i>0:
plus.append(i)
else:
minus.append(i)
for i in range(0, len(minus),1):
k = i+1
while(k!=len(minus)):
answer = minus[i] + minus[k]
#print("minus[i]",minus[i])
#print("minus[k]", minus[k])
if(answer*-1 in plus):
maybe_list = [minus[i],minus[k],answer*-1]
maybe_list.sort()
if((maybe_list.count(0)<=zeros)):
total.add(tuple(maybe_list))
k+=1
for i in range(0, len(plus),1):
k = i+1
while(k!=len(plus)):
answer = plus[i] + plus[k]
#print("minus[i]",minus[i])
#print("minus[k]", minus[k])
if(answer*-1 in minus):
maybe_list = [plus[i],plus[k],answer*-1]
maybe_list.sort()
if((maybe_list.count(0)<=zeros)):
total.add(tuple(maybe_list))
k+=1
return [list(t) for t in total]
오랫동안, 고민하다가 다른 코드를 보았다. ㅠ 조금 아쉬우면서도
2개의 pivot을 이용하는 것을 생각하지 못하였다.
2개의 pivot을 이용하는 방법은 다음과 같다.
일단 for 문으로, index 0 부터 len(nums)-2 까지 돈다. (-2 까지 도는 이유는 비교하는 값이 3개 필요하기 때문)
이후, i+1 값을 left, len(nums)-1 값을 right로 둔다.
| (i) | (left) | | | | | | | | | (right) |
이런식으로 구성이된다.
만약 i + left + right가 음수라면, left를 한칸 오른쪽으로 옮겨, 0과 값이 가까워지도록 한다.
반대의 경우라면, right를 한칸 왼쪽으로 옮긴다.
이를 반복하기 위해, left<right일 때 동안 위 과정을 반복한다.
만약 합이 0이 될 경우엔, 해당 값을 list에 따로 넣어준다.
그 과정에서, nums[left] == nums[left +1] 이라면, left를 한칸 더 옮겨 준다.
왜냐하면,
| (i) | (left) | | | | | | | | | (right) |
이렇게 값을 구한 이후,
| (i) | | (left) | | | | | | | | (right) |
이렇게 또 값을 구하는 것은 같은 과정을 반복하는 것이기 때문이다. [(left)의 값이 동일한 경우]
-> right도 동일하게 while 문을 돌려준다.
따라서 skip 해준다.
처음에는, 이 방법이 -1, -1, 2 와 같은 경우를 무시하게 되는 것이 아닌가 생각했었다.
하지만, 해당 케이스는 이미, skip 되기 전에 list에 append 되었다. 즉, 이미 고려되었다.
또한 다음 for 문을 돌 때, 이전 nums[i] == nums[i-1] 인지 확인해주어, 같은 for 문을 2번 돌지 않도록 한다.
이 또한, -1, -1, 2 와 같은 경우를 무시하는 것이 아닌가 걱정하였지만,
만약 그럴 경우에는, or nums[i] == nums[i+1] 인지도 확인 했을 때이지 않을까 싶다.
아래의 경우야 말로, -1, -1, 2를 무시하는 것이 아닌가 싶다.
if i>0 and nums[i] == nums[i-1] or nums[i] == nums[i+1]:
continue
중복되는 지 확인하는 것을 i+1, i-1 둘 중 하나를 기준으로 진행했기 때문에,
-1, -1, 2 도 고려 가능하다.
따라서,
nums[i] 가
| | (i) | (left) | | | | | | | | (right) |
nums[i-1] 과 동일한 경우,
| (i) | (left) | | | | | | | | | (right) |
nums[i-1] 에서 nums[i] 의 경우를 이미 계산 완료한 상태이기 때문에, continue를 진행한다.
다음에 더 비슷한 문제를 만나게 되면, 더 잘 풀 수 있으리라 생각한다.
2. 코드
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
list = []
for i in range(0,len(nums)-2, 1):
if i>0 and nums[i] == nums[i-1]:
continue
left = i+1
right = len(nums) -1
while(left<right):
total = nums[i] + nums[left] + nums[right]
if total < 0:
left +=1
elif total > 0:
right -=1
else:
list.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 list
solution = Solution()
print(solution.threeSum([0,-1,-1,2]))
'코딩 테스트 > leetcode' 카테고리의 다른 글
[leetcode 2024/02/06] 232. Implementing Queue using Stacks (1) | 2024.02.06 |
---|---|
[leetcode 2024/02/06] 225. Implement Stack using Queues (0) | 2024.02.06 |
[leetcode 2024/02/06] 561. Array Partition (0) | 2024.02.06 |
[leetcode 2024/02/05] 5.Longest Palindromic Substring (1) | 2024.02.05 |
[leetcode 2024/02/05] 49. Group Anagrams (1) | 2024.02.05 |