4. 알고리즘 정리 [투 포인터]

투 포인터의 대표 적인 예제는 아래와 같다.

리스트 A가 있고, 타겟값 S가 있다.

이 리스트에서 두수의 합이 타겟값 S가 되는 걸 찾는다고 가정하면?

리스트 1개씩 비교해 가면서 체크를 할수있겠지만. 리스트의 크기에 따라, 시간 복잡도는 정비례하게된다.

 

그러면 이럴 경우에는 ? 리스트를 정렬하고 투포인터 알고리즘을 사용하면 된다.

 

사용 방법은 아래 순서와 같다.

1. 리스트를 오름차순으로 정렬한다.

2. 포인터 left는 리스트의 시작점을 포인터 right는 리스트의 끝점을 가리킨다.

3. left 와 right가 만날때까지 다음을 반복한다.

 3-1. left + right 의 합이 타겟 값과 같으면 출력, 
 3-2. left + right 가 타겟 값보다 작으면 left 1증가
 3-3 left + right 가 타겟 값보다 크면 , right 1감소

 

해당 방법으로 문제를 풀어 나간다.

 

 

* 두수의 합

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

3273번: 두 수의 합

 

일단, 배열이 엄청 많아질 것을 대비해서, 메모리나 다른 제약을 두어 무조건 투포인터를 두고 계산하게 한다.

매커니즘은 간단하다.

그냥 맨처음과 끝을 투포인터로 두고, 합한걸, 비교해서 작으면  start를 올리고 크면 end를 줄인다.

같으면, count 를 추가하고, start를 높인다.

투포인터는 다만, int 배열이 sort가 되어야 한다.

그래서, Arrays.stream으로 받을때, sorted 함수를 추가해서, 정렬된 형태를 유지할수있도록 한다.

 

 

*두 용액

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

2470번: 두 용액

 

 

두용액에 대한 얘기지만, 리스트에서 음수 + 양수를 해서 0이랑 같은 값을 찾으면된다.

 

차이는 거의없고 매커니즘도 동일하지만, 차이가 있다면,

별도 변수에 절대값이 0에 가까울수록, 즉 작을수록 min이라는 변수에 넣어주면서 체크를 하면되고,

0보다 클떄는 end를 줄여가고, 아닌경우에는 start를 늘려서 점점 값을 키우게끔 하면된다.

즉 if를 두가지케이스로 세우면된다.