백준 11728. 배열합치기

🅰 백준 11728. 배열합치기

11728번: 배열 합치기

✏️ 문제 풀이

• mergesort의 전형적인 문제이다.
• 배열을 나눠서 다시 합치는 과정을 통해 정렬을 하는데 합치는 부분만 따로 구현을 해주었다.
• 이미 입력 데이터는 정렬되어 있기 때문에 arrN 배열과 arrM배열을 0번째 부터 탐색을 해줘서 더 작은 수를 sb에 추가해주었다.
• 만약 index를 배열 끝까지 다 방문하였다면 if문을 이용하여 그 배열을 제외한 다른 배열의 데이터를 계속해서 넣어주었다.

✏️ 소스코드

package divideandconquer;

/*이분탐색 X , mergesort 합병정렬O*/
import java.util.*;
import java.io.*;

public class Main_실버5_11728_배열합치기 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(st.nextToken());
		int arrN[] = new int[N];
		int M = Integer.parseInt(st.nextToken());
		int arrM[] = new int[M];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arrN[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			arrM[i] = Integer.parseInt(st.nextToken());
		}
		int ns = 0, ms = 0;
		int cnt = -1;
		while (++cnt != N + M) {
			if (ms == Integer.MAX_VALUE) {
				sb.append(arrN[ns]+" ");
				ns += 1;
				continue;
			} else if (ns == Integer.MAX_VALUE) {
				sb.append(arrM[ms]+" ");
				ms += 1;
				continue;
			}
			if (arrN[ns] > arrM[ms]) {
				sb.append(arrM[ms]+" ");
				if (ms + 1 < M)
					ms += 1;
				else
					ms = Integer.MAX_VALUE;
			} else if (arrN[ns] <= arrM[ms]) {
				sb.append(arrN[ns]+" ");
				if (ns + 1 < N)
					ns += 1;
				else
					ns = Integer.MAX_VALUE;
			}
		}
		System.out.println(sb);
	}
}

 

✅ 후기

• 이분탐색으로 풀었으나 시간초과가 계속나서 mergesort로 해결하였다. 시간복잡도, 공간복잡도에 대해 더 공부해야겠다.