Two pointers

리스트에 순차적으로 접근해야 할 때 '두 점'의 위치를 기록하면서 처리하는 알고리즘

 

문제

첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.

세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.

네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.

각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

 

given

3
1 3 5
5
2 3 6 7 9

일 때 [1 2 3 3 5 6 7 9]의 배열이 나와야 한다.

 

일반적으로 배열을 합친 후 sort를 진행하거나, sorting이 되어있는 컬렉션으로 진행 시 걸리던 O(n log n)의 시간 복잡도를

 

투 포인터 알고리즘을 이용함으로써 O(n)으로 줄일 수 있다.

 

풀이는 다음과 같다.

public class Main {
	public ArrayList<Integer> solution(int n, int m, int[] arr, int[] arr2){
		ArrayList<Integer> answer = new ArrayList<>();
		int p1=0, p2=0;
		while(p1<n && p2<m) {
			if(arr[p1] < arr2[p2]) answer.add(arr[p1++]);
			else answer.add(arr2[p2++]);
		}
		while(p1<n) answer.add(arr[p1++]);
		while(p2<m) answer.add(arr2[p2++]);
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = kb.nextInt();
		}
		int m = kb.nextInt();
		int[] arr2 = new int[m];
		for(int j=0; j<m; j++){
			arr2[j] = kb.nextInt();
		}
		for(int x : T.solution(n, m, arr, arr2)) {
			System.out.print(x + " ");
		}
	}
}

 

n배열과 m배열이 먼저 끝날때까지를 비교해놓고, 한쪽이 끝나면 나머지를 모두 추가하는 방식으로 구현한다.