자바 알고리즘 문제 풀이 Two pointers, Sliding window Q01_두 배열 합치기

설명

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.

입력

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

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

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

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

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

출력

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

예시 입력1	예시 출력
3 1 3 5 5 2 3 6 7 9	1 2 3 3 5 6 7 9

 

코드

내가 입력한 코드

package twoPointers_SlidingWindow;

import java.util.Scanner;

public class Q01 {
	public int[] solution(int n, int[] arr1, int m, int[] arr2) {
		int[] answer = new int[n+m];
		int tmp = 0;
		for (int i = 0; i < answer.length; i++) {
			if(i >= arr1.length) {
				answer[i] = arr2[i-arr1.length];
			}else {
				answer[i] = arr1[i];				
			}
			
			tmp = answer[i];
			int x = 0;
			for (int j = 0; j <= i; j++) {
				if(answer[j] > tmp) {
					x = answer[j];
					answer[j] = tmp;
					tmp = x;
					answer[i] = x;
				}
			}
		}
		
		return answer;
	}
	public static void main(String[] args) {
		Q01 T = new Q01();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr1 = new int[n];
		for (int i = 0; i < n; i++) {
			arr1[i] = kb.nextInt();
		}
		
		int m = kb.nextInt();
		int[] arr2 = new int[m];
		for (int i = 0; i < m; i++) {
			arr2[i] = kb.nextInt();
		}
		
		for(int x:T.solution(n, arr1, m, arr2)) {
			System.out.print(x + " ");
		}
	}
}

 

---

해설 코드

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+" ");
	}
}

 

 

풀이 및 정리 

배열 합치기 문제로써 제일 간단한 문제이다.
나는 배열로 받았는데 ArrayList를 사용하면 좀 더 효율적인 코드로 작성할 수 있다.

풀이에서는 ArrayList를 만들고 p1, p2 변수를 만들어 인덱스 변수로 사용하였다.
while문을 통해 정수 배열 n, m에서 각각의 인덱스를 비교해 작은 값을 ArrayList의 answer 변수에 순서대로 넣어준다. 그렇게 하다 보면 두 배열 중 하나의 배열은 answer에 다 들어갔지만 나머지 배열의 원소들은 들어가지 않았을 수 있다. 그래서 추가로 whlie문을 통해 남은 원소들의 값을 answer에 넣어준다.