•
문제 설명 : 제공된 숫자목록 중 2개를 골라 더 했을 때 target 숫자보다 작은 경우의 수를 구하는 문제
•
풀이 방법
◦
일반적으로 O(N^2) 으로 순회하며 푸는 문제는 맞다. 그 방식으로도 solved가 가능하다.
◦
하지만, 이 문제는 sorting 문제이기 때문에 sorting을 활용하여 시간 복잡도를 더 줄여볼 수 있다.
▪
동일한 O(N^2) 이지만, sorting을 활용하면 탐색을 최대한 줄일 수 있다.
•
시간복잡도 :
•
성공 코드
class Solution:
def countPairs(self, nums: List[int], target: int) -> int:
result = 0
# 오름차순 정렬
nums.sort()
# 큰 수를 하나씩 확인하며, 작은 숫자와 더한다.
for i in range(len(nums)-1, -1, -1):
for j in range(i):
# 범위를 넘어선다면, 바로 break하여 탐색을 최대한 줄인다.
if nums[i] + nums[j] < target:
result += 1
else:
break
return result
Python
복사
•
개선 코드(O(NlogN))
투포인터를 접목시켜 탐색을 줄인 방법이다.
탐색 부분의 시간 복잡도가 O(N^2) → O(N)으로 변경되었다.
class Solution:
def countPairs(self, nums: List[int], target: int) -> int:
result = 0
# 배열을 정렬합니다.
nums.sort()
left = 0
right = len(nums) - 1
while left < right:
if nums[left] + nums[right] < target:
# 현재 left부터 right까지 모든 쌍이 조건을 만족합니다.
# (left, left + 1), (left, left + 2) ... (left, right)
result += (right - left)
# 작은 수 쪽의 포인터를 이동시켜 합산 값을 키워 재탐색한다.
left += 1
else:
# 큰 수쪽의 포인터를 줄여 합산 값을 줄여 재탐색한다.
right -= 1
return result
Python
복사
