3273_두수의 합

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

3273번: 두 수의 합

 

 

처음 문제를 보면 for문을 두번 돌려서 문제를 풀었을 것 같다.

 

하지만 문제에서도 나와있듯이 투 포인터 알고리즘을 사용해서 풀라고 한다!

 

투 포인터 알고리즘이란 1차원 배열에서 공간을 가리키는 두개의 포인터를 지니는 방식으로 특정값을 추출해내는 알고리즘이다.

 

인터넷을 좀 뒤져서 공부를 해보니 투 포인터에는 몇가지 방법이 있다.

 

크게 두가지가 있는데 배열의 시작과 끝에서 시작하는 방법과 두 포인터 모두 시작점에서 시작하는 방법이다.

 

 

위 문제는 start포인터는 시작에서, end 포인터는 끝에서 시작해서 좁혀가는 방법으로 구할 수 있다.

 

1 2 3 4 5

 

위와같은 1차원 배열이 있다고 생각해보면, start는 1, end는 5에서 시작해서 두수의 합이 목표값보다 크다면 end를 1칸 앞으로 당기고 작다면 start를 1칸 뒤로 옮기면 된다.값과 일치한다면 값을 저장하거나 count를 세주고 star를 한칸 띄워주면 된다. 그리고 두 점이 만난다면 종료해주면 된다

 

 

 

n = int(input())
lst = list(map(int,input().split()))
lst.sort()
x = int(input())

start,end,cnt =0,n-1,0

while start < end:
    s = lst[start] + lst[end]
    if s < x:
        start +=1
    elif s > x:
        end -= 1
    else:
        cnt +=1
        start +=1
print(cnt)