#백준_11728 배열 합치기 - Java

# 처음에는 병합 정렬로 접근하였음. 출력에 있어 System.out.print는 당연히 시간 초과, Stringbuilder, BufferWriter를 사용했는데도 시간 초과가 떠서 그냥 PriorityQueue를 사용하여 해결하였다.

 

질문 검색에 들어가서 확인도 해봤는데 자바에는 시간리미트를 수정해줘야 할거 같다. 어디에서 봤는데 Arrays.Sort로도 성공한 사람이 있다고 하였음.

< 정답 코드 >

package bj;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class p11728 {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		PriorityQueue pq = new PriorityQueue<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		while(st.hasMoreTokens())
			pq.offer(Integer.parseInt(st.nextToken()));
		
		st = new StringTokenizer(br.readLine());
		while(st.hasMoreTokens())
			pq.offer(Integer.parseInt(st.nextToken()));
		
		while(!pq.isEmpty())
			bw.write(pq.poll()+" ");
		
		bw.close();
	}
}

 

 

 

 

병합 정렬 코드도 첨부는 하지만, 통과는 못한 코드입니다. 틀린게 보이신다면 조언 부탁드립니다.

package bj;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class p11728_timeout {
	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());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int arr[] = new int[N+M];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i=N; i<M+N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		mergeSort(arr, 0, M+N-1);
//		StringBuilder sb = new StringBuilder();
		for(int i=0; i<M+N; i++) {
			bw.write(arr[i]+" ");
//			sb.append(arr[i]+" ");
		}
		bw.flush();
		
	}
	public static void mergeSort(int arr[], int m ,int n) {
		if(m<n) {
			int middle = (m+n)/2;
			mergeSort(arr, m, middle);
			mergeSort(arr, middle+1, n);
			merge(arr,m, middle, n);
		}
	}
	
	public static void merge(int arr[], int m, int middle, int n) {
		int i = m;
		int j = middle+1;
		int t=1;
		int tmp[] = new int[arr.length+1];
		
		while(i<=middle && j<=n) {
			if(arr[i] < arr[j]) {
				tmp[t++] = arr[i++];
			}else {
				tmp[t++] = arr[j++];
			}
		}
		
		while(i<=middle) {
			tmp[t++] = arr[i++];
		}
		while(j<=n)
			tmp[t++] = arr[j++];
		
		i = m;
		t = 1;
		
		while(i <= n)
			arr[i++] = tmp[t++];
	}
}