99클럽(2기) 코테 스터디 1일차 TIL # Sorting # Two Pointers

LeetCode 2824. Count Pairs Whose Sum is Less Than Target

Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] < target.

* 1 <= nums.length == n <= 50
* -50 <= nums[i], target <= 50

 

• 문제: n개의 integer로 구성된 array 'nums'와 integer 'target'이 주어졌을 때, 아래 조건을 만족하는 (i, j) 쌍의 개수를 반환
• 조건: 0 <= i < j < n and nums[i] + nums[j] < target

---

1. 첫 번째 풀이 (시간복잡도: O(n^2))

1) answer값 초기화

  answer 값을 0으로 초기화한다. 

 

2) 조건을 만족하는 nums의 인덱스 (i, j) 쌍 찾기

 이중 for문으로 0부터 'nums의 요소의 개수 - 1'의 범위를 반복한다. 각 for문의 반복자는 i와 j로 설정했으며, i와 j는 nums의 인덱스를 의미한다. i가 j보다 작고, nums[i] + nums[j] < target라는 조건을 만족하면 answer에 1을 더했다. 최종적으로 모든 순회를 마쳤을 때 계산된 answer를 반환한다.

 

 이중 for문이므로 nums의 모든 요소을 n번 방문하는 로직을 두번 타게 되어 시간복잡도는 O(n*n) 즉, O(n^2)가 된다.

 

 풀긴 풀었고, nums의 요소 개수가 최대 50개이므로 O(n^2)도 괜찮다고 생각했지만, 발표한 분의 문제 풀이를 듣고 시간복잡도 개선이 필요하다는 생각이 들었다. 

def solution(self, nums: List[int], target: int) -> int:
    answer = 0
    n = len(nums)
    for i in range(n):
        for j in range(n):
            if i < j and nums[i] + nums[j] < target:
                answer += 1
    return answer

 

 

2. 두 번째 풀이 (시간복잡도: O(nlogn))

 Sorting과 Two Pointers를 이용해서 문제를 풀었다. 

 

1) nums 정렬

 조건을 만족하는 (i, j) 쌍을 찾기 전, 우선 nums를 정렬한다. nums를 정렬하는 이유는 왼쪽 포인터를 가장 작은 값에서 시작해서 큰 값 방향으로 탐색해나가고, 오른쪽 포인터를 가장 큰 값에서 시작하여 작은 값 방향으로 탐색해나감으로써 모든 경우의 수를 효율적으로 탐색하기 위함이다. 참고로 파이썬 리스트의 sort 메소드는 Tim Sort 알고리즘을 사용하며 Tim Sort의 시간복잡도는 O(nlogn)이다.

 

2) answer 값, i를 가리키는 left 값, j를 가리키는 right 값 초기화

 answer의 초기값은 0, left의 초기값은 'nums의 첫 번째 요소의 인덱스'를 의미하는 0, right의 초기값은 'nums의 마지막 요소의 인덱스'를 의미하는 'nums 요소 개수에서 1을 뺀 값'이다. 

 

3) 조건을 만족하는 nums의 인덱스 (i, j) 쌍 찾기

 조건을 만족하는 left(i)와 right(j)를 찾기 위해 반복문을 사용해야 하는데 언제 반복이 끝날 지 모르므로 while 반복문을 사용했다. 반복문의 조건은 ' left < right'로 설정함으로써 문제의 '0 <= i < j < n' 조건을 만족시켰다. 반복문 안에서는  nums[left] + nums[right] < target을 만족하는 경우와 그렇지 않은 경우를 기준으로 분기를 나눈다.

 

 nums[left] + nums[right] < target 를 만족한다면 answer에 포함되는 (i, j) 쌍은 right에서 left를 뺀 수만큼 있을 것이므로 answer에 right - left만큼 더해준다. 더 정확히 얘기하자면 i(left)를 기준으로 하고 있으므로 j의 개수를 세는 것이다. 그 후 left 포인터를 한 칸 오른쪽으로 이동시킨다.

 

 nums[left] + nums[right] < target 를 만족하지 않을 경우에는 right 포인터를 왼쪽으로 이동시킨다. left 포인터와 right 포인터가 만날 때까지 left는 오른쪽으로, right 포인터는 왼쪽으로 이동하면서 모든 경우의 수를 탐색하게 된다. 모든 탐색을 마치면 left = right가 되고 while 조건에 따라 반복문을 빠져나오며, 반복문을 탈출하기 전까지 더해진 최종 answer를 반환한다.

  

 while문 안에서는 각 포인터가 배열의 각 요소를 한 번씩만 방문하므로 O(n)의 시간복잡도를 갖는다. 따라서 Sorting으로 인한 시간복잡도 O(nlogn)와 Two Pointers로 인한 시간복잡도 O(n)을 더해 최종 시간복잡도는 O(nlogn)이 된다.

 

from typing import List

def countPairs(self, nums: List[int], target: int) -> int:
    nums.sort()
    answer = 0
    left = 0 # nums의 첫 번째 요소의 인덱스
    right = len(nums) - 1 # nums의 마지막 요소의 인덱스(nums 요소의 개수에서 1을 뺀 값)

    while left < right:
        if nums[left] + nums[right] < target: # nums[left] + nums[right] < target 조건을 만족한다면 
            answer += (right - left) # answer에 오른쪽 포인터가 가리키는 인덱스에서 왼쪽 포인터가 가리키는 인덱스를 뺀 값을 더함
            left += 1 # 왼쪽 포인터를 한 칸 오른쪽으로 이동
        else: # 조건을 만족하지 않는다면 오른쪽 포인터를 한 칸 왼쪽으로 이동
            right -= 1

    return answer

 

 

3. 느낀점

 단순히 문제 풀이하는 것만 중요한 게 아니고 어떻게 하면 시간복잡도를 줄일 수 있을지에 대한 고민이 항상 필요하다는 것을 다시 한번 느낀다. 이 문제에서는 nums의 요소 개수가 최대 50개로 제한이 되어 있었지만 실무에서는 그렇지 않은 경우가 대부분이니.. 대부분의 경우 트레이드오프를 따진다면 시간복잡도를 고려하는 게 이득일 것이다!