투 포인터. [3273]

[1. 문제 설명]

n 개의 서로 다른 양의정수로 이루어진 수열에서 

두 수의 합이 x 가 되는 쌍의 개수를 찾는다.

 

 

[2. 풀이 접근]

투 포인터 란?

배열 형태에 자료 구조에 순차적으로 접근 해야 할 때, 

배열 내 두개의 위치를 기록하면서 하는 방식

병합정렬에서 나눈 두 배열을 다시 병합하는 방식을 생각하면 된다..

 

   ↓                                         ↓

[head] ........[mid].......[tail]

 

포인터 혹은 index 를 각각 배열의 시작(head) 과 끝(tail) 에 위치 시키고,

head 또는 tail 을 이동시키면서 처리하는 방식

 

head 와 tail 이 역전되는 순간 탐색을 종료하게 된다.

 

특별한 경우 간단하게 생각할 수 있는 O(N²) 알고리즘을

O(N) 으로 풀 수 있게 해준다.

 

가급적 정렬 시킨 배열에서 유용한 것 같다.

 

이 문제는 투 포인터와 별개의 방식으로 풀 수 있다.

 

=== A. 값이 위치하는 index 를 저장하여 처리 ===

수열 내 두 원소의 값이 어떤 값과 일치해야 하기 때문에

하나의 원소를 알면 다른 하나의 원소는 정해지게 된다.

 

이 원소의 index 가 존재하는 지 확인하기 위한 배열을 준비해야 한다.

 

이 방법에서 주의해야 할 점은 크게 두가지가 있다.

 

첫번째는 index 를 찾기 위한 배열의 최대 길이이다.

x 값이 2,000,000 이고, 어떤 수열의 값이 1 일 때, 더해서 x 가 되기 위해서는 1,999,999 가 필요하다.

이 값은 수열 내에 존재하진 않지만 (수열 내 원소들은 모두 1,000,000 이하)

별도의 예외처리를 하지 않는 한, 원소 값의 index 탐색을 위한 배열에 index 로서 사용되게 된다.

 

두번째는 또 다른 원소의 값이 자기 자신인 경우이다.

x=2 이고 a[0]=1 일 때, 필요 한 다른 값은 1 이다.

 

그러나 수열 내 모든 원소는 다르다고 하였으므로,

이 경우는 처리 되어서는 안된다.

 

 

=== B. 투 포인터를 이용 한 풀이 ===

먼저 배열을 정렬하도록 한다.

문제의 i < j 라는 조건이 있지만, 출력의 형태는 원소 쌍의 개수 이므로

i < j 라는 순서는 그렇게 중요하지 않다.

오히려 중복 쌍을 세지 않도록 하는 것이 더 중요하다.

 

A[0] = 100, A[1] = 3 이고, x = 103 일 때

i = 0, j = 1 이지만, 개수를 셀 때는

A[0] 이 굳이 100 일 필요는 없다는 것이다.

 

정렬 후 head 와 tail 을 위치시키고,

각 위치에서 두 원소의 합을 확인한다.

 

같다면 찾은 것이고 head 와 tail 을 모두 이동시키고,

다르다면 head 와 tail 을 적절히 이동 시켜야 한다.

 

배열이 정렬되었기 때문에

합이 x 보다 작다면 head 를 이동시키고 (두 합이 커지는 것이 보장된다.)

크다면 tail 을 이동시켜야 한다. (두 합이 작아지는 것이 보장된다.)

 

풀이 A 는 정렬을 할 필요가 없지만, 메모리 사용량이 크며,

풀이 B 는 정렬을 해야 하지만, 메모리 사용량이 훨씬 적다.

 

 

[3. 코드-A]

 

 

[3. 코드-B]