[Algorithm] 투 포인트(Two-Point Algorithm)

✨ 투 포인트(Two-Point Algorithm)

2개의 포인터를 이용하여 배열속 원하는 값을 찾을수있다.
O(N)의 시간 복잡도를 가진다.

 

 

 

 

ex) 백준 두 수의 합

https://www.acmicpc.net/problem/3273

import sys

n=int(sys.stdin.readline().rstrip())
li=list(map(int,sys.stdin.readline().rstrip().split(" ")))
correct=int(sys.stdin.readline().rstrip())
li.sort()
left_p=0
right_p=n-1
count=0

while True:
 
    if(li[left_p]+li[right_p]==correct):    #같을때
        left_p+=1
        count+=1
    elif(li[left_p]+li[right_p]<correct):   #합이 더 작음
        left_p+=1
    elif(li[left_p]+li[right_p]>correct):   #합이 더 큼
        right_p-=1

    if(left_p>=right_p):break   #끝

print(count)

 

양쪽 끝의 포인터로 정렬된 리스트를 탐색하여 값을 얻어냈다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🎈참고자료