Sort / Two Pointer

0. 배경 지식

정렬

임의의 배열

[3, 1, 5, 6]

을 정렬하는 시간 복잡도는 O(nlogn) 이다

버블 정렬 등등 여러가지 정렬 방식이 있지만 파이썬에서는 이미 잘 만들어져 있다.

Two Pointer

위와 같은 배열이 있을때 3과 6이라는 두개의 포인터를 지정해서 왔다갔다 하며 문제를 해결하는 방법이다. 주의할 점은 정렬이 된 후에 사용한다

1. 문제 이해하기

2023.12.06 - [coding test] - Two Sum

Two Sum

이전 글과 같은 문제이다. 이전 글에서는 완전 탐색으로 풀었지만 이번엔 정렬과 Two Pointer을 사용해서 풀어보자

2. 접근 방법

자료구조와 알고리즘을 사용하여 새로운 접근방법을 도출한다

위 문제의 배열은 정렬이 되어있지 않은 배열이니까 정렬 알고리즘을 사용하여 정렬을 해보면 새로운 접근 방법이 생기지 않을까 ??

접근 과정

1. 위의 풀이방법은 반복문이 중첩되어서 n^2의 시간 복잡도이다.(시간이 부족할 수 있다)

2. 더 효율적인 방법을 찾아야 하는데 정렬이 안되어있으니까 정렬을 해보자

2-1. 마침 정렬의 시간 복잡도는  nlogn 이기 때문에 해볼 가치가 있다.

3. 정렬을 했을 경우 [1, 3, 4, 5, 7 , 9, 16] 인데 예를 들어서 4, 7 두개의 포인터를 잡았을때 11로 작다

3-1. 오름차순 정렬이 되어있으니까 오른쪽으로 한칸씩 움직여볼까?

단순화

1. [1, 3, 4, 5, 7 , 9, 16] 이 배열을 [1, 3, 16] 으로 단순화

2. 1과 16을 포인터로 지정

2-1. 1 + 16은 17로 11보다 크다 (11 < 17)

2-2. 결과 숫자가 target 보다 크다면 오른쪽 숫자를 한칸 옮긴다

3. 1 + 3 은 4로 11보다 작다 (4 < 11 < 17)

3-1. 결과 숫자가 target 보다 작다면 왼쪽 숫자를 한칸 옮긴다

4. 하지만 오른쪽 포인터와 왼쪽 포인터가 같은 숫자를 가리킨다면 비교할 필요가 없다(조건에서 제한했음)

=> 같은 숫자가 없는 것으로 판단

4-1. 같은 숫자를 가리킨 상태에서 한칸을 더 옮길 필요도 없다(어차피 숫자가 더 커지거나 작아지거나 할 뿐)

적용

1. [1, 3, 4, 5, 7 , 9, 16] 양 끝 숫자인 1과 16을 포인터로 잡는다

2. 1 + 16 은 17로 target(11)보다 크다

2-1. 오른쪽 숫자 (16)을 왼쪽으로 한칸 옮긴다

3. 1 + 9 는 8로 target 보다 작다

3-1. 왼쪽 숫자를 오른쪽으로 한칸 옮긴다

4. 3 + 9 는 12 로 target 보다 작은 숫자이다

4-1. 왼쪽 숫자를 오른쪽으로 한칸 옮긴다

5. 5 + 9 는 14로 target 과 같다

3. 풀이

def twoSum(nums, target):
  nums.sort() # 1. 정렬
  l , r = 0 , len(nums) -1 # 2. 투 포인터 잡기

  while(l < r): # 3. 작은 포인터가 큰  포인터 보다 작으면 실행 (같아지거나 커지면 실행 중지)
    # 4. 포인터 크기 비교 시작
    if nums[l] + nums[r] < target: # 4-1. 더한 숫자가 작다면 왼쪽 숫자 오른쪽으로 이동
      l += 1
    elif nums[l] + nums[r] > target: # 4-2. 더한 숫자가 크면 오른쪽 숫자 왼쪽 이동
      r -= 1
    else:
      return True # 4-3. target 과 같다면 true
  return False