문제 이해

"정렬 되어 있는 배열" A, B가 있다.
A,B 배열을 합쳐 재정렬 시키는 문제이다.

---

문제 풀이

여기서 강조해야 할 부분은 "정렬 되어 있는 배열"이다.
즉, A[a] < B[b]일 경우, A[0] < A[1] < ... < A[a-1] < A[a] < B[b]이다.
반대의 경우도 마찬가지이다.

따라서 2개의 포인터를 준비했다.
1개는 A의 index를 나타내는 index_a 포인터, 나머지는 B의 index를 나타내는 index_b 포인터이다.
그리고 아래와 같이 포인터를 움직인다.

1. A[index_a] < B[index_b] : A[index_a] 값을 정답 배열에 추가시킨다. 이후, index_a를 1증가시킨다.

2. A[index_a] > B[index_b] : B[index_b] 값을 정답 배열에 추가시킨다. 이후, index_b를 1 증가시킨다.

이 때 주의해야 할 점은 index_a와 index_b가 각각 A,B의 범위를 넘어버리는 경우는 따로 고려해줘야 한다는 점이다.
만약, 그 점을 고려하지 않는다면 ArrayIndexOutOfBoundesException이 발생할 것이다.

하지만, 이 경우 A와 B는 모두 "정렬 되어 있는 배열"이므로, 아직 배열에 추가되지 않은 나머지 수들을 순차적으로 입력만 하면 될 것이다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
	
	static int N, K;
	static int[] ans;
	static int[] arr, arr2;
	static int index = 0;
	
	
	static void sum() {
		int index1 = 0;
		int index2 = 0;
		
		for(int i =0;i<N+K;i++) {
			if(index1>=N) {
				ans[i] = arr2[index2];
				index2++;
				continue;
			}
			if(index2>=K) {
				ans[i] = arr[index1];
				index1++;
				continue;
			}
			
			if(arr[index1] > arr2[index2]) {
				ans[i] = arr2[index2];
				index2++;
			}
			else {
				ans[i] = arr[index1];
				index1++;
			}
		}
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		K = sc.nextInt();
		
		ans = new int[N+K];
		
		arr = new int[N];
		for(int i =0;i<N;i++) {
			arr[i] = sc.nextInt();
		}
		
		arr2 = new int[K];
		for(int i =0;i<K;i++) {
			arr2[i] = sc.nextInt();
		}
		
		
		sum();
		
		StringBuilder sb = new StringBuilder();
		for(int s:ans) {
			sb.append(s+" ");
		}
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 3,4번째 시간 초과 : Arrays.sort로 시간 문제를 해결할 수 있지 않을까 싶었지만, 불가능했다.
• 2번째 시간 초과 : StringBuilder를 활용하지 않고 System.out.print(s+" ")를 통해 모두 출력 하여 출력에 대한 시간 초과가 발생하였다.