[Ch.03 - 투 포인터] 1. 두 배열 합치기

1. 두 배열 합치기

 

설명

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

입력

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

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

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

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

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

출력

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

 

예시 입력 1 

3
1 3 5
5
2 3 6 7 9

예시 출력 1

1 2 3 3 5 6 7 9

---

#배열만 이용

package string.ch01;

import java.util.Scanner;

public class asdf {
	public int[] solution(int[] arr1, int[] arr2, int n, int m) {
		int[] answer = new int[n + m];
		int p1 = 0;
		int p2 = 0;
		for (int i = 0; i < n + m; i++) {
			if (p1 < n && p2 < m) {
				if (arr1[p1] <= arr2[p2])
					answer[i] = arr1[p1++];
				else
					answer[i] = arr2[p2++];
			}
			else if (p1 < n)
				answer[i] = arr1[p1++];
			else if (p2 < m)
				answer[i] = arr2[p2++];
		}
		return answer;
	}

	public static void main(String[] args) {
		asdf T = new asdf();
		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 j = 0; j < m; j++) {
			arr2[j] = kb.nextInt();
		}
		for (int X : T.solution(arr1, arr2, n, m)) {
			System.out.print(X + " ");
		}
	}
}

 

+) 세련된 풀이 [배열리스트 이용]

1. while(p1<n && p2<m) 

->p1보다 p2가 가리키는 값이 클 때, p1이 가리키는 값을 추가하고, 이후에 p1을 증가시킨다.

2. while(p1<n)

-> p1이 n보다 작을 경우 반복해서 추가

3. while(p2<m)

-> p2가 n보다 작을 경우 반복해서 추가

package twopointer.ch03;
//두 배열 합치기
//두 배열에 포인터를 각각 사용해 -> 크기를 비교해서 하나의 배열로 추가 
import java.util.ArrayList;
import java.util.Scanner;

class Twopointer01_2 {

	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) {
			 //p1이나 p2가 작으면 계속 반복
			 if(a[p1]<b[p2]) {
				 answer.add(a[p1++]);
				 //p1이 가리키는 값을 추가하고, 이후에 p1을 증가시킨다.
			 }
			 else {
				 answer.add(b[p2++]);
			 }			 
		 }
		 while(p1<n){
			 //p1이 n보다 작을 경우 계속 반복
			 answer.add(a[p1++]);
		 }
		 while(p2<m){
			 //p2가 m보다 작을 경우 계속 반복
			 answer.add(b[p2++]);
		 }
		 

		return answer;
	}

	public static void main(String[] args) {
		Twopointer01_2 T = new Twopointer01_2();
		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 j = 0; j < m; j++) {
			b[j] = kb.nextInt();
		}

		for (int x : T.solution(n, m, a, b)) {
			System.out.print(x + " ");

		}
	}

}

---

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    
    int n=in.nextInt();
    int[] arr1 = new int[n];
    for(int i=0;i<n;i++){
      arr1[i]=in.nextInt();
    }
    
    int m=in.nextInt();
    int[] arr2= new int[m];
    for(int i=0;i<m;i++){
      arr2[i]=in.nextInt();
    }
    
    int[]answer = new int[n+m];
    int len=answer.length;
    
    int lt=0;
    int rt=0;
    
    for(int i=0;i<len;i++){
      if(lt<n&&rt<m){
        if(arr1[lt]<=arr2[rt]) answer[i]=arr1[lt++];
        else answer[i]=arr2[rt++];
      }
      else{
        if(lt<n||rt<m){
          if(lt<n) answer[i]=arr1[lt++];
          if(rt<m) answer[i]=arr2[rt++];
     	 }
      }
    }
    
    for(int x:answer) System.out.print(x+" ");
  }
}

-> while문으로 변경

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    
    int n=in.nextInt();
    int[] arr1 = new int[n];
    for(int i=0;i<n;i++){
      arr1[i]=in.nextInt();
    }
    
    int m=in.nextInt();
    int[] arr2= new int[m];
    for(int i=0;i<m;i++){
      arr2[i]=in.nextInt();
    }
    
    int[]answer = new int[n+m];
    int len=answer.length;
    
    int lt=0;
    int rt=0;
    int i=0;
    while(lt<n&&rt<m){
        if(arr1[lt]<=arr2[rt]) answer[i++]=arr1[lt++];
        else answer[i++]=arr2[rt++];
    }
    while(lt<n) answer[i++]=arr1[lt++];
    while(rt<m) answer[i++]=arr2[rt++];
    
    for(int x:answer) System.out.print(x+" ");
  }
}

---

+)03.02

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n1 = in.nextInt();
    int[] arr1 =new int[n1];
    for(int i=0;i<n1;i++){
      arr1[i]=in.nextInt();
    }
    int n2 = in.nextInt();
    int[] arr2 =new int[n2];
    for(int i=0;i<n2;i++){
      arr2[i]=in.nextInt();
    }
    Main main= new Main();
    for(int x: main.solution(arr1, arr2)) 
      System.out.print(x+" ");
  }
  public ArrayList<Integer> solution(int[] arr1, int[]arr2){
    int p1 = 0;
    int p2 = 0;
    ArrayList<Integer> list = new ArrayList<>();
    while(p1!=arr1.length && p2!=arr2.length){
      if(arr1[p1]<=arr2[p2]){
        list.add(arr1[p1++]);
      }else{
        list.add(arr2[p2++]);
      }
    }
    while(p1!=arr1.length) list.add(arr1[p1++]);
    while(p2!=arr2.length) list.add(arr2[p2++]);
    return list;
  }
}