BOJ : 백준 11728 배열 합치기(JAVA)

문제

정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.
배열 A의 크기 = N, 배열 B의 크기 = M
시간 제한 : 1.5초, 메모리 제한 : 256MB

입력
N M
배열 A의 값들
배열 B의 값들

풀이

이미 정렬되어 있는 배열이므로 합친 후 배열하는 것보다는 바로바로 비교해가며 새 array에 넣는 방식을 선택하기로 했다!

a는 배열 A에서 사용할 index, b는 배열 B에서 사용할 index이다.
a<N 혹은 b<M인 동안
A[a]<=B[b]면 resultArray[i]에 A[a]를 넣고, a와 i를 늘린다.
B[b]가 더 크다면 resultArray[i]에 B[b]를 넣고, b와 i를 늘린다.

a, b 둘 중 하나라도 본인 array의 크기와 같아진다면
둘 중 덜 들어간 array를 찾아 남은 것들을 전부 resultArray에 넣어준다.

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

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());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int i = 0;
		int[] A = new int[N];
		st = new StringTokenizer(br.readLine());
		for(i=0; i<N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] B = new int[M];
		st = new StringTokenizer(br.readLine());
		for(i=0; i<M; i++) {
			B[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] res = new int[N+M];
		int a = 0, b = 0;
		i = 0;
		while(a < N && b < M) {
			if(A[a] <= B[b]) {
				res[i++] = A[a++];
			} else {
				res[i++] = B[b++];
			}
		}
		
		
		while(a<N) {
			res[i] = A[a];
			a++; i++;
		}
		while(b<M) {
			res[i] = B[b];
			b++; i++;
		}
		
		
		for(int num : res) {
			bw.write(num + " ");
		}
		bw.flush();
		bw.close();
	}

}

처음에 BufferedWriter가 아닌 System.out.print를 사용하였다가 시간 초과가 났다.. 🥹 시간 초과가 날 부분은 없는 것 같아 곰곰히 생각해보다 혹시나 하고 바꿨는데 맞아서 기쁘다!

문제를 풀며

쉬워서 푸는 데 얼마 걸리지 않았다ㅎㅎ 앞으로 풀 때 이렇게 느끼는 문제가 많아지길...

앞으로는 BufferedWriter를 사용해야겠다..

다른 풀이 방법으로 두 배열을 합친 뒤 sort하는 방법이 있었다.
Java의 Array.sort()는 뭔가... 편법을 쓰는 느낌이라 잘 안 쓰게 된다. 학교에서 C언어를 사용해서 Merge Sort 등 다양한 소팅을 구현해볼 때 애먹었는데, 자바에서는 한 방에 되다니........
그렇다고 아예 안 쓰는 건 아니고..ㅎㅎ 편리해서 나도 소팅해야 될 땐 종종 사용하고 있다