[BAEKJOON] 백준 분할정복 11728 :: 배열 합치기

 

💬  문제 설명

정렬되어있는 두 배열 A와 B가 주어진다.

두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.

 

🔨  입출력 예

입력 

• 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)
• 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다.
• 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다.

 

출력

• 첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다.

 

예제 입력 1)

2 2
3 5
2 9

 

예제 출력 1)

2 3 5 9

 

예제 입력 2)

2 1
4 7
1

 

예제 출력 2)

1 4 7

​

예제 입력 3)

4 3
2 3 5 9
1 4 7

 

예제 출력 3)

1 2 3 4 5 7 9

​

​

💻  Main.java

• 투 포인터, 분할 정복 문제
• 각각의 포인터 i,j를 이용해 배열의 크기를 비교 후, 오름차 순 정렬해준다.
• 크기를 모두 비교후 남은 배열을 출력해준다.

/* 백준 분할정복 - 11728 :: 배열 합치기 */
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in ));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int[] arr1 = new int[n];
		int[] arr2 = new int[m];
		
		st = new StringTokenizer(br.readLine());
		for(int k = 0; k < n; k++)
			arr1[k] = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		for(int k = 0; k < m; k++)
			arr2[k] = Integer.parseInt(st.nextToken());
		
		int i = 0, j = 0;
		StringBuilder sb = new StringBuilder();
		while(i < n && j < m) {
			if(arr1[i] < arr2[j]) {
				sb.append(arr1[i] + " ");
				i++;
			}
			else {
				sb.append(arr2[j] + " ");
				j++;
			}
		}
		
		while(i < n) {
			sb.append(arr1[i] + " ");
			i++;
		}
		
		while(j < m) {
			sb.append(arr2[j] + " ");
			j++;
		}
		
		System.out.println(sb);
		
		br.close();
	}
}