[JAVA] 두 배열 합치기

출처 - 인프런

 

접근하기

 

처음엔 입력받은 원소들을 배열에 담아야겠다고 생각했는데

첫 번째 배열과 두 번째 배열의 크기가 다를 경우도 감안해야 돼서, 배열보다는 리스트가 낫겠다고 생각했다.

그래서, 두 개의 리스트를 만든 다음에 각각의 리스트에 원소를 넣고

최종적으로 두 배열의 원소를 합친 리스트에서 정렬 후에 출력하면 되겠다고 생각했다.

 

TO-DO

1. 정수 N을 입력 받고 반복문으로 첫 번째 리스트에 원소 값들을 넣는다.

2. 정수 M을 입력 받고 반복문으로 두 번째 리스트에 원소 값들을 넣는다.

3. 새로운 리스트를 만들고 첫 번째 리스트와 두 번째 리스트의 원소 값들을 넣는다.

4. 해당 리스트를 오름차순으로 정렬하고 출력한다.

 

 

코드

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

  
public class Main {
  public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		List<Integer> list = new ArrayList<>();
		int N = sc.nextInt();
		for(int i = 0; i < N; i++) {
			list.add(sc.nextInt());
		}
		int M = sc.nextInt();
		for(int i = 0; i < M; i++) {
			list.add(sc.nextInt());
		}
		Collections.sort(list);
		for(int i : list) {
			System.out.printf("%d ", i);
		}
	}
}

 

리뷰

 

풀고나서 풀이 영상을 보니, 해당 문제는 two pointers algorithm 문제라고 해서

two pointer를 만들어서 풀어도 보았다.

 

 

그림과 같이 p1, p2 두개의 값을 0으로 초기화 하고, 각 배열의 0번째 원소값들을 바라보게 한다.

 

iArr[p1] 값과 jArr[p2]의 값을 비교한 다음,

더 작은 값을 list에 담고 더 작은 값을 가르키는 포인터의 값을 증가한다.

 

단, p1, p2 각각의 포인터는 해당 배열의 마지막 원소까지만 이동할 수 있도록 해야한다.

포인터가 어느 하나의 배열의 마지막까지 다다랐으면

나머지 배열의 원소를 list에 담고 해당 배열의 포인터를 증가시킨다.

 

Two Pointers를 적용한 코드

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
  
public class Main {
  public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] iArr = new int[N];
		for(int i = 0; i < N; i++) {
			iArr[i] = sc.nextInt();
		}
		
		int M  = sc.nextInt();
		int[] jArr = new int[M];
		for(int i = 0; i < M; i++) {
			jArr[i] = sc.nextInt();
		}
		
		List<Integer> list = new ArrayList<Integer>();
		
		int p1 = 0, p2 = 0;
		while(p1 < N && p2 < M) {
			if(iArr[p1] < jArr[p2]) {
				list.add(iArr[p1]);
				p1++;
			} else {
				list.add(jArr[p2]);
				p2++;
			}
		}
		while(p1 < N) {
			list.add(iArr[p1]);
			p1++;
		}
		while(p2 < M) {
			list.add(jArr[p2]);
			p2++;
		}
		
		for(int i : list) {
			System.out.printf("%d ", i);
		}
		
	}
}