백준 11728번: 배열 합치기 [정렬][투 포인터] -Java

https://www.acmicpc.net/problem/11728

11728번: 배열 합치기

굳이 굳이 투포인터를 써보자?

 

<Java코드 - 투 포인터 알고리즘 적용>

시간복잡도 O(N+M)

package algorithm.boj;

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

public class Boj11728 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int res[] = new int[N+M];
		int arr1[] = new int[N];
		int arr2[] = new int[M];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr1[i] = Integer.parseInt(st.nextToken());
		}
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			arr2[i] = Integer.parseInt(st.nextToken());
		}
		
		
		int residx = 0;
		int idx1 = 0;
		int idx2 = 0;
		
		while(idx1 < N && idx2 < M) {
			if(arr1[idx1] < arr2[idx2]) {
				res[residx++] = arr1[idx1++];
			} else {
				res[residx++] = arr2[idx2++];
			}
		}
		
		if(idx1<=N-1) {
			for (int i = idx1; i < N; i++) {
				res[residx++] = arr1[i];
			}
		}
		
		if(idx2<=M-1) { 
			for (int i = idx2; i < M; i++) {
				res[residx++] = arr2[i];
			}
		}
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i = 0; i < N+M; i++) {
			bw.write(res[i]+" ");
		}
		
		bw.flush();
		bw.close();
	}

}

 

 

<Java 코드  - 정렬알고리즘 적용>

N+M만큼 배열에 그냥 다 입력받고 마지막에 Arrays.sort 때려버리기

 

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));
				
		StringBuilder sb = new StringBuilder();
		sb.append(br.readLine());
		
		StringTokenizer st = new StringTokenizer(sb.toString());
		
		int arr[] = new int[Integer.parseInt(st.nextToken()) + Integer.parseInt(st.nextToken())];
		int idx = 0;
		
		st = new StringTokenizer(br.readLine());
		
		while(st.hasMoreTokens()) {
			arr[idx++] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		while(st.hasMoreTokens()) {
			arr[idx++] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		for(int i : arr) {
			bw.write(i +" ");
		}

		bw.flush();
		bw.close();
	}

}