[백준] 11728번 : 배열 합치기

문제

정렬된 배열 두 개가 주어졌을 때

두 배열을 정렬된 상태로 합치는 문제

 

접근 방식

{2, 3, 5, 9}
{1, 4, 7}

 

위와 같은 배열이 두 개 주어졌을 때

1, 2, 3, 4, 5, 7, 9

순서대로 정렬해야 한다.

 

두 개의 배열은 이미 정렬된 상태이니

각 배열의 첫 번째 인덱스들부터 서로 비교하며

작은 순서대로 다른 배열에 추가하거나 출력해주면 된다.

 

병합 정렬의 개념에 대해서 공부하기 좋은 문제로

이미 정렬된 두 개의 배열이 주어지기 때문에 풀기가 쉬웠다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		String[] input1 = br.readLine().split(" ");
		String[] input2 = br.readLine().split(" ");

		int[] A = new int[n];
		int[] B = new int[m];

		for (int i = 0; i < n; i++) {
			A[i] = Integer.parseInt(input1[i]);
		}

		for (int i = 0; i < m; i++) {
			B[i] = Integer.parseInt(input2[i]);
		}

		int aIdx = 0;
		int bIdx = 0;

		for (int i = 0; i < n + m; i++) {
			if (aIdx == n) {
				sb.append(B[bIdx++]).append(" ");
			} else if (bIdx == m) {
				sb.append(A[aIdx++]).append(" ");
			} else if (A[aIdx] >= B[bIdx]) {
				sb.append(B[bIdx++]).append(" ");
			} else {
				sb.append(A[aIdx++]).append(" ");
			}
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}