sort & Two Pointer

1. 정렬의 시간복잡도

정렬이 되지 않은 리스트를 정렬할때 시간복잡도는 O(nlogn)이다!(그냥 외울것)

2. Two Pointer

arr = [1,3,5,7,2]

예를들어 위 같은 리스트가 있을 때 두개의 포인터를 가지고 문제를 해결하는 방법이다. 예를들면 1과 2를 가지고 좌우로 왔다갔다 하면서 해결하는 방법이 있겠다. 하지만 Two Pointer는 정렬이 된 상태에서 이용한다.

3. 활용하기

비교를 위하여 전에 풀었던 문제를 가져오겠다.

2023.06.22 - [coding test] - 알고리즘

이 글의 마지막에 있는 문제이다. 코드를 다시 가져오자면

def towSum(nums, target):
    n = len(nums)
    print(n)

    for i in range(n):
        for j in range(i+1, n):
            if nums[i] + nums[j] == target:
                return True
    return False

O(n^2)의 시간 복잡도가 걸리는 풀이이다.

현재 풀이는 정렬을 하지 않은 풀이 방법이다. 만약 정렬을 하면 O(nlogn)의 시간 복잡도가 걸리니까 더 짧겠다 생각하며 다른 방법도 생각해본다.

4. 문제 적용

4-1. 접근

arr = [1,3,4,5,7,9,16]

1. 정렬을 해봤을 때 가장 중앙에 있는 4와 7을 더했을 때 11이다.

2. 정렬이 되어 있으니 한칸씩 올리면?

3. 더 크다면 한칸씩 내리면?

4-2. 확장

위의 배열에서 양끝의 숫자인 1과 16을 더해보자 17이 나온다 우리가 원하는 숫자는 14이니까 원하는 숫자보다 크다

16을 왼쪽으로 옮겨보자, 1 + 9 =10 

그럼 왼쪽에 있던 1을 한칸 옮겨보자 3 + 9 = 12

10보단 크지만 14보다는 작다

또 작은 수를 한칸 더 옮겨본다 4 + 9 = 13 아직 14보다 작다

다시 작은 수를 한칸 옮겨본다 5 + 9 = 14 정답

이걸 두개의 타겟이 같은 수를 가리킬때 까지 해주면 된다. 만약 같은 수를 가리킨다면 맞는 숫자가 없을 것

4-3. 코드 설계

1. nums.sort()

2. 가장 왼쪽 수 : l, 가장 오른쪽 숫자 : r

인덱스로 봤을 때 l = 0, r = n-1(리스트 요소 개수가 n개라고 가정) length는 1부터 시작하기 때문에 리스트 요소의 수보다 -1 해주면 항상 맨끝의 index가 나올것임

3. nums[l] + nums[r] == target 이 맞는지 확인

3-1. 통과하면 true

3-1. 두개 더한값이 크다면?

3-1-1. r을 r-1 해준다(한칸 왼쪽으로 옮겨준다)

3-1-2. 작다면 l을 l+1(한칸 오른쪽으로 옮겨준다)
3-2. 이걸 l == r 일때 까지(같은수를 가리킬때 까지) 반복해줄 것

3-3. 같은 수에 도달했다면 false 

4-4. 코드 제작

def towSum(nums, target):
    n = len(nums)
    nums.sort()
    l, r = 0, n-1
    while l < r:  # l이 r보다 작을때는 계속 반복문을 돌 것이기 때문에 while 선택
        if nums[l] + nums[r] > target:
            r -= 1
        elif nums[l] + nums[r] < target:
            l += 1
        elif nums[l] + nums[r] == target:
            return True
    return False

더 작은 시간 복잡도로 코드를 만들었다.