Sort & Two Pointer

파이썬에는 기본적으로 오름차순으로 sort를 해주는 메소드가 있다. sort의 시간복잡도는 O(nlogn)이다.

 

Tow Pointer

보통 sort와 tow pointer는 같이 사용된다. 예를 들어서 설명하겠다.

[9, 3, 2, 6]

위와 같은 list가 있다. 위의 list를 오름차순으로 정열하면

[2, 3, 6, 9]

 ^           ^

Tow pointer를 한글로 하면 두지점이다. 두 지점을 왼쪽 끝과 오른쪽 끝에 두 지점이 있다고 생각하자. list 내에 있는 숫자를 더해서 우리가 원하는 값이 있는지 확인을 할거다. 더해서 10이 있는지 확인을 하면 왼쪽과 오른쪽 두지점을 일단 더한다.

11이 나오고 우리가 원하는 값 10보다 더한값이 크다. 그럼 왼쪽에 오른쪽에 있는 포인트를 한칸 왼쪽으로 이동한다

[2, 3, 6, 9]

 ^       ^

이동한 두 지점을 더하면 8이된다.  8은 10보다 작은값이다. 더한값을 올려야하니 왼쪽에 있는 포인트를 한칸 오른쪽으로 이동한다.

[2, 3, 6, 9]

     ^   ^

두 포인트를 더하면 9가 나온다. 여전히 10보다 작다. 왼쪽에 있는 값을 오른쪽으로 이동하려고 보니 오른쪽에 있는 포인트랑 만나게 된다. 두 값이 만나면 중복된 값을 더하게 되니 더이상 list내에서 더한 값이 10이 될 수 있는 경우가 없다는걸 확인했다. 

위의 예시처럼 양쪽 끝지점에서 두지점의 연산된 값에 따라서 목표값으로 다가가는 과정으로 Sort와 Two Pointer를 사용했다. 

 

실제로 파이썬에서 코드를 작성하면 다음과 같다.

 

list = [4, 2, 1, 7, 5, 9, 10]


def findTarget(list, target):
    l, r = 0, len(list)-1
    list.sort()
    while l < r:
        if list[l] + list[r] < target:
            l += 1
        elif list[l] + list[r] > target:
            r -= 1
        elif list[l] + list[r] == target:
            return True
    return False


print(findTarget(list, 22))  # false
print(findTarget(list, 19))  # true