[JAVA][BOJ][S5] 11728. 배열 합치기

11728번: 배열 합치기

문제

정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)

둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다.

출력

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

풀이

정렬을 이용해 푸는 간단한 문제다 크게 두 가지 방법을 이용해 풀어 봤는데, 하나는 배열, 하나는 리스트로 푸는 방법이다

arraylist와 list의 시간 차이가 궁금해서 그것까지 해 봤는데 유의미한 차이를 보이는 것 같지는 않다

https://read-me.tistory.com/entry/JAVABOJS5-11004-K%EB%B2%88%EC%A7%B8-%EC%88%98

비슷한 문제인 윗 글에서는 배열은 시간 초과가 나고 리스트가 더 시간이 짧게 나왔는데 이번 문제는 반대의 결과가 나왔다 궁금한데 둘 다 배열을 받아서 정렬하는 식은 같은데 왜인지 잘 모르겠다

아마 K번째 수 문제는 숫자를 하나만 찾고, 이번 문제는 모든 수를 다 출력해야 해서 리스트보다 배열의 읽기 속도가 더 빠른 것 같다

코드

package 문제풀이;

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

public class S5_11728_배열합치기 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
//		int[] arr = new int[N+M];						// 풀이 1
//		ArrayList<Integer> list = new ArrayList<>();	// 풀이 2
		List<Integer> list = new ArrayList<>();			// 풀이 3
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
//			arr[i] = Integer.parseInt(st.nextToken());
			list.add(Integer.parseInt(st.nextToken()));
		}
		
		st = new StringTokenizer(br.readLine());
		for (int i = N; i < N+M; i++) {
//			arr[i] = Integer.parseInt(st.nextToken());
			list.add(Integer.parseInt(st.nextToken()));
		}
		
//		Arrays.sort(arr);
		Collections.sort(list);
		
		for (int i = 0; i < N+M; i++) {
//			sb.append(arr[i] + " ");
			sb.append(list.get(i) + " ");
		}
		
		System.out.println(sb);

	}

}

결과

아래부터 풀이 1, 2, 3이다

 

#자바 #java #boj #백준 #알고리즘