섹션 3. 투 포인터 & 슬라이딩 윈도우 - 1. 두 배열 합치기

📌 문제 설명

오름차순으로 정렬된 두 배열이 주어질 때 두 배열을 오름차순으로 병합하여 출력하는 프로그램을 작성합니다.

---

📝 입력 & 출력

입력

• 첫 줄: 첫 번째 배열의 크기 N (1 ≤ N ≤ 100)
• 둘째 줄: N개의 오름차순 정수
• 셋째 줄: 두 번째 배열의 크기 M (1 ≤ M ≤ 100)
• 넷째 줄: M개의 오름차순 정수

출력

• 오름차순으로 정렬된 하나의 배열을 한 줄로 출력

---

🔸 예제 입력 & 출력

예제 입력 1

3
1 3 5
5
2 3 6 7 9

 

예제 출력 1

1 2 3 3 5 6 7 9

---

💡 해결 방법

• 두 배열은 이미 정렬되어 있으므로 투 포인터 기법을 사용하여 효율적으로 병합할 수 있습니다.
• 두 포인터 p1, p2를 이용하여 각 배열의 현재 위치를 비교하면서 결과 배열에 작은 값을 추가합니다.

---

💻 코드 구현 (Java)

package partTwoPointers;

import java.util.*;

public class Problem1 {
	public ArrayList<Integer> solution(int n, int m, int[] arr1, int[] arr2){
		ArrayList<Integer> result = new ArrayList<>();
		int p1 = 0, p2 = 0;
		
		while(p1 < n && p2 < m) {
			if(arr1[p1] < arr2[p2]) result.add(arr1[p1++]);
			else result.add(arr2[p2++]);
		}
		while(p1 < n) result.add(arr1[p1++]);
		while(p2 < m) result.add(arr2[p2++]);
		
		return result;
	}
	
	public static void main(String[] args) {
		Problem1 T = new Problem1();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr1 = new int[n];
		for(int i = 0; i < n; i++) arr1[i] = kb.nextInt();
		
		int m = kb.nextInt();
		int[] arr2 = new int[m];
		for(int i = 0; i < m; i++) arr2[i] = kb.nextInt();
		
		for(int x : T.solution(n, m, arr1, arr2)) {
			System.out.print(x + " ");
		}
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 포인터 초기화

int p1 = 0, p2 = 0;

• 각 배열의 현재 위치를 나타내는 포인터입니다.

2️⃣ 투 포인터 병합

while(p1 < n && p2 < m) {
	if(arr1[p1] < arr2[p2]) result.add(arr1[p1++]);
	else result.add(arr2[p2++]);
}

• 두 포인터가 유효한 범위 내에 있을 때, 더 작은 값을 결과 리스트에 추가합니다.

3️⃣ 남은 값 추가

while(p1 < n) result.add(arr1[p1++]);
while(p2 < m) result.add(arr2[p2++]);

• 한 배열이 먼저 끝나면, 남은 배열의 모든 값을 그대로 결과에 추가합니다.

---

⏳ 시간 복잡도 분석

• 두 배열을 한 번씩 순회하므로 O(N + M)의 시간 복잡도를 가집니다.

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런