메모
배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 전부 출력하라
이때, 인덱스값 i, j, k는 전부 다른 수임
브루트포스가 있고
combinations가 있을듯 (인덱스의 중복이 없으므로 combinations를 선택)
-
특이한게, 결과값의 각 원소들이 정렬된 상태로 있네..?
- 일단 젤 앞에 sort를 해주긴 하는데
- 정렬된 리스트를 가지고 뭔가 속도나 이런 측면에서 최적화한 방법이 있을라나?
- 정렬된 결과물이 시간초과 극복할 힌트같은데
-
시간초과 결과를 보고 깨달은 후ㅋ
-
피벗값(중앙값) 찾아서 걔를 기준으로 좌/우 나눌까?
-
내가 말하는 중앙값은 음수랑 양수를 구분하는 값임
-
음수끼리 더할필요 없고, 양수끼리 더할필요 없자나 값이 0이 나와야하니까
- 이때 두가지 케이스임
- 왼쪽에서 오면서 왼쪽+1인애 포함 3개
- 오른쪽에서 오면서 오른쪽-1인애 포함 3개
-
알고리즘 및 방법
- 브루트포스랑 combinations 말고
- 피벗을 찾고 양옆에서 오는거 이렇게 짜보자
- 이런 느낌으로
- 결론적으로 말하면 틀렸음
- 히든테케에서 막힘 (해설은 맨밑에)
일단 sort()
pivot = bisect_left(0) # 0 또는 음수와 양수가 갈라지는 위치의 인덱스값을 찾음(lowerbound)
for left in range(pivot-1):
for right in range(len(nums), pviot+1, -1):
# 왼쪽, 왼쪽+1 오른쪽
sub = [nums[left], nums[left+1], nums[right]]
if sum(sub) == 0 and sub not in result:
ans.append(sub)
# 왼쪽, 오른쪽-1, 오른쪽
sub = [nums[left], nums[right-1], nums[right]]
if sum(sub) == 0 and sub not in result:
ans.append(sub)
솔루션 코드 - 내가 푼 - 1차 접근
- combinations사용
- 시간초과
- not in 에서 끝났음 O(n)이니까
- 시간초과
from itertools import combinations
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# combinations를 사용한 방식 - 시간초과 (이게아닌가?)
result = []
nums.sort()
C = combinations(nums, 3)
for c in C:
if sum(c) == 0 and list(c) not in result:
result.append(list(c))
return result- 브루트포스
- 마찬가지 시간초과
- O(n^4)가되네
- for문 3개에 in 연산자도 O(n)이라서...
- 책에서도 브루트포스 방법을 제시했으나
- O(n^3)이므로 시간초과여서 틀렸다고 설명함
- 참고로 책에선 in을 안쓰고, 중복을 제고하기 위해 다음 코드를 씀
if i > 0 and nums[i] == nums[i-1]: continue
- O(n^3)이므로 시간초과여서 틀렸다고 설명함
- 암튼 코드는 이럼
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 2차접근
result = []
nums.sort()
for i in range(len(nums)):
for j in range(i+1, len(nums)):
for k in range(j+1, len(nums)):
if nums[i]+nums[j]+nums[k] == 0 and [nums[i],nums[j],nums[k]] not in result:
result.append([nums[i],nums[j],nums[k]])
return result
솔루션 코드 3차 접근 - 투포인터
- 위에서 왼/오 나눠서 하겠다고 한 방식 코드
- 시간초과는 해결하였으나 (O(n^2))
- 아니다 근데 in을 그대로 썼었네.. 해결못한 셈인가
- 히든테케에서 절망을 느낌
from bisect import bisect_left
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 3차 접근 : 투포인터로 왼/오 이동하면서 계산 -> 시간초과는 해결한듯 하나 새로운 문제점 찾음(히든테케)
result = []
if len(nums) == 3 and sum(nums) == 0:
result.append(nums)
return result
nums.sort()
pivot = bisect_left(nums, 0)
for left in range(pivot-1):
for right in range(len(nums)-1, pivot, -1):
sub = [nums[left], nums[left+1], nums[right]]
if sum(sub) == 0 and sub not in result:
result.append(sub)
sub = [nums[left], nums[right-1], nums[right]]
if sum(sub) == 0 and sub not in result:
result.append(sub)
return result
히든테케 주의사항
1)
Input [0,0,0,0]
Output [[0,0,0]]
2) 이런거도 안될듯
Input [0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output [[0,0,0]]
솔루션 코드 - 책
- 브루트포스 말고 투포인터 솔루션만 정리함
- O(n^2)풀이법
- 정렬을 시켜주자
- 일단 이동하면서 중복값일 경우 continue로 건너뛴다
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue- 그리고 i의 다음 지점과 마지막 지점을 left, right로 지정하고
- i일 때 i의 다음 좌-끝 에서 하나씩 이동하며 sum을 체크한다
- 쓰리포인터이고, 이진탐색 조건걸 때랑 비슷한 느낌의 풀이임
- sum < 0이면 left를 오른쪽으로 이동하며 값을 키워준다 (정렬되어있으니까)
- sum > 0이면 right를 왼쪽으로 이동하며 값을 줄여준다
- sum == 0이면 값을 정답에 추가하고
- left의 오른쪽, right의 왼쪽이 같은 값일 경우, 다른 값이 나올 때까지 이동해줌
- 다른값을 찾았으면 마지막으로 한번 더 ++해주고(현재 left right가 ++된상태가 아니니까) 다음 while문으로 감
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 책 솔루션 : 생각은 비슷하나 좀 다르다
results = []
nums.sort()
for i in range(len(nums) - 2):
# 중복된 값 건너뛰기 (위에 for문 조건 걸 필요없이 if에 0이상일때 쓰면 되네)
if i > 0 and nums[i] == nums[i-1]:
continue
# 간격을 좁혀가며 합 sum 게산 <-- 나랑 다른 부분
left, right = i+1, len(nums)-1
while left < right:
suma = nums[i] + nums[left] + nums[right]
if suma < 0:
left += 1
elif suma > 0:
right -= 1
else:
# sum = 0인 경우이므로, 정답추가
results.append((nums[i], nums[left], nums[right]))
# 그리고 left, 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
Do My Best