프로그래밍 언어 및 IT 정보/알고리즘

[Algorithm] 투포인터(Two Pointer) 알고리즘 with python

Himer_torr 2022. 7. 27. 11:55
반응형

'투포인터' 란?

이름 그대로 두 가지의 포인터를 사용하여 문자열이나 배열(or 리스트)에서 원하는 값을 찾거나

반복문을 써야할 때 쓰기 좋은 방식입니다.

 

그냥 기본 방식인 탐색(반복문)을 쓰다 보면 시간이 오래 걸리거나 시간 초과가 걸리는 경우에 

투포인터를 사용하면 메모리와 시간 효율성을 높일 수 있습니다!

시간복잡도 : O(N)  기본 탐색 반복문을 사용한다면 O(N^2)

 

투포인터는 2가지 방식이 있습니다

  • 앞에서 시작하는 포인터와 끝에서 시작하는 포인터
  • 빠른(Fast runner)가 느린 (slow runner)보다 앞서는 형식

 

형식 1. 앞에서 시작하는 포인터 끝에서 시작하는 포인터

 

 

쉬운 예제를 통해서 한번 이해해보도록 하겠습니다.

 

Q . 주어진 배열에서 합이 27인 경우를 찾아라

 



풀이

1. 시작점(start)과 끝점(end)을 정하여 1, 28을 가리킨다.

2. 찾아야 하는 값(27)이 두 점의 합보다 작으면 end 포인터를 감소시킨다. (1, 25)

3. 찾아야 하는 값(27)이 26보다 크면 start 포인터를 증가시킨다 (3,25)

4. 계속 진행하면서 값을 비교하고 양쪽 포인터가 동일한 값(12,12)을 가리키면 더 이상 만족할 조건이 없으므로 종료한다.

 

여기서 중요한 점은 배열의 중복 수 가 없어야 하고,
수열이 정렬되어 있어야 합니다.

arr = [3, 9, 25, 22, 1, 6, 5, 11, 19, 28, 17, 12, 16] # 주어진 배열. 중복 수 없음
S = 27 # 목표 합계
arr.sort()
start, end = 0, len(arr) - 1
while start <= end:
    
    if arr[start] + arr[end] > S:
        end -= 1
    elif arr[start] + arr[end] < S:
        start += 1
    elif arr[start] + arr[end] == S:
        print(start, '번째 수 (', arr[start], ') + ', end, '번째 수 (', arr[end], ')')
        end -= 1
        start += 1

결과 값

형식 2. 빠른 포인터가 느린 포인터보다 앞서는 형식(토끼와 거북이)

 

이번엔 토끼와 거북이 알고리즘을 사용해보도록 하겠습니다.

 

쉬운 예제를 사용해보겠습니다.

 

숫자가 들어가 있는 정렬된 배열에서 중복되는 숫자를 제거하고 새로운 배열의 길이를 출력해보시오.

 

Input : [0,0,1,1,1,2,2,3,3,4]

Output : 5

 

풀이

1. 두포인터 slow와 fast는 각각 인덱스0과 1에서 시작한다.

2. fast가 인덱스 1부터 증가하게 되면서 조건(두포인터의 숫자가 다르면)이 맞으면 slow를 앞으로 이동한 후, 그 숫자를 fast 포인터         가 가리키는 숫자로 바꿔준다.

 

 

이 loop를 반복하다 보면 배열이 arr = [0,0,1,1,1,2,2,3,3,4]에서
arr= [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]로 바뀌고 slow+1이 중복된 숫자가 없는 길이로 출력하면 됩니다.

arr = [0,0,1,1,1,2,2,3,3,4] # 주어진 배열. 
slow = 0

for fast in range(1,len(arr)):    
    if arr[slow] != arr[fast]:
        slow +=1
        arr[slow] = arr [fast]
    

print("Output : ", slow+1)

 

반응형