투 포인터 알고리즘

투 포인터 알고리즘

2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.

 

 

• 투 포인터 알고리즘을 활용하여 2개의 그룹을 병합하는 과정

- 시간 복잡도 : O(N + M) (N, M : 정렬된 배열 A와 B의 데이터 개수)

 

[ 예시 ]

 

1. 정렬된 배열 A와 B를 입력받는다.
2. 배열 A에서 처리되지 않은 원소 중 가장 작은 원소를 data 1 index가 가리키도록 한다.
3. 배열 B에서 처리되지 않은 원소 중 가장 작은 원소를 data 2 index가 가리키도록 한다.
4. A[data 1 index]와 B[data 2 index] 중에서 더 작은 원소를 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다.
5. 배열 A와 B에서 더 이상 처리할 원소가 없을 때까지 2~4번의 과정을 반복한다.

 

 

 

 

 

* <Do It! 알고리즘 코딩테스트 with C++편>, <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 참고하였습니다.