[알고리즘]두 배열 합치기 및 오름차순 정렬

▷ 문제

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을

오름차순으로 합쳐 출력하는 프로그램을 작성하세요.

* 입력

첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.

세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.

네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.

각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

* 출력

오름차순으로 정렬된 배열을 출력합니다.

▷ 입력 예시

3

1 3 5

5

2 3 6 7 9

▷ 출력 예시

1 2 3 3 5 6 7 9

▷ 풀이

1. 다중 for문 사용

import java.util.Scanner;

public class Main {	
	public int[] solution(int n, int m, int[] nArr, int[] mArr){
		int[] answer = new int[n+m];
		int index = 0;

		//먼저 nArr을 넣어줍니다.
		for(int i=0; i<n; i++){
			answer[i] = nArr[i];
		}
        
		//answer의 남은 공간에 mArr을 넣어줍니다.
		for(int i=n; i<n+m; i++){
			answer[i] = mArr[index++];
		}

		return ascend(answer);
	}

	public static int[] ascend(int[] n){
		// 선택 정렬
		for(int i=0; i<n.length; i++){
			for(int j=0 ; j<n.length; j++){
				if(n[j] > n[i]){
					int temp = n[i];
					n[i] = n[j];
					n[j] = temp;
				}
			}
		}

		return n;
	} 

	public static void main(String[] args){
		Main main = new Main();
		Scanner kb = new Scanner(System.in);

		int n = kb.nextInt();
		int[] nArr = new int[n];

		for(int i=0; i<n; i++){
			nArr[i]=kb.nextInt();
		}

		int m = kb.nextInt();
		int[] mArr = new int[m];

		for(int i=0; i<m; i++){
			mArr[i]=kb.nextInt();
		}

		for(int x :main.solution(n, m, nArr, mArr)){
			System.out.print(x + " ");
		}
	}
}

 

2. 포인터 사용

import java.util.*;
class Main {	
	public ArrayList<Integer> solution(int n, int m, int[] a, int[] b){
		ArrayList<Integer> answer = new ArrayList<>();
		int p1=0, p2=0; // 포인터 변수 선언
        
		while(p1<n && p2<m){
			if(a[p1]<b[p2]) answer.add(a[p1++]);
			else answer.add(b[p2++]);
		}
        
        	//둘 중 남은 배열을 넣어줍니다. 오름차순 된 상태로 입력받았으므로 그대로 넣어주면 됩니다.
		while(p1<n) answer.add(a[p1++]);
		while(p2<m) answer.add(b[p2++]);
        
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
        
		int n=kb.nextInt(); 
		int[] a=new int[n];
		for(int i=0; i<n; i++){
			a[i]=kb.nextInt();
		}
        
		int m=kb.nextInt();
		int[] b=new int[m];
		for(int i=0; i<m; i++){
			b[i]=kb.nextInt();
		}
        
		for(int x : T.solution(n, m, a, b)) System.out.print(x+" ");
	}
}

▷ 핵심 포인트

1. 배열 합치기

   Stream, System.arraycopy, Collections와 list 사용 등 다양한 방법을 이용하여 쉽게 구현할 수 있습니다.

2. 배열 오름차순 정렬

  arrays.sort()를 사용하여 구현할 수 있습니다.

3. 이중 for문이 아닌 포인터 변수를 이용한 풀이는 시간복잡도를 줄일 수 있습니다.