[JAVA] 알고리즘 문제 - 두 배열 합치기

두 배열 합치기 

설명

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

 

입력

첫 번째 줄에 첫 번째 배열의 크기 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 section3;

import java.util.ArrayList;
import java.util.Scanner;

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

        int n = kb.nextInt();  // 첫 번째 배열의 크기 입력
        int[] a = new int[n];
        System.out.println("a =>" + a);
        for (int i = 0; i < n; i++) {
            a[i] = kb.nextInt();  // 첫 번째 배열의 원소 입력
            System.out.println("원소입력");
        }

        int m = kb.nextInt();  // 두 번째 배열의 크기 입력
        int[] b = new int[m];
        System.out.println("b = " + b);
        for (int i = 0; i < m; i++) {
            b[i] = kb.nextInt();  // 두 번째 배열의 원소 입력
            System.out.println("i = " + i);
        }

        ArrayList<Integer> result = t.solution(n, m, a, b);
        for (int x : result) System.out.print(x + " ");
        System.out.println();  // 모든 결과 출력 후 줄바꿈 추가

        kb.close();  // Scanner를 닫아서 추가적인 입력을 받지 않도록 합니다.
    }

    private 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;
    }
}

 

 

초기입력값

n = 3
a = [1,3,5]
m = 5
b = [2,3,6,7,9]

 

두배열의 병합 -> 초기 상태

a = [1, 3, 5]
b = [2, 3, 6, 7, 9]
answer = []
p1 = 0, p2 = 0

 

첫번째 비교 및 추가

a[p1] = 1, b[p2] = 2
1 < 2 -> answer에 1 추가, p1 증가
answer = [1]
p1 = 1, p2 = 0

 

두번째 비교 및 추가

a[p1] = 3, b[p2] = 2
3 > 2 -> answer에 2 추가, p2 증가
answer = [1, 2]
p1 = 1, p2 = 1

 

세번째 비교 및 추가

a[p1] = 3, b[p2] = 3
3 = 3 -> answer에 3 추가, p2 증가
answer = [1, 2, 3]
p1 = 1, p2 = 2

 

 

---

남은 요소 추가

첫 번째 배열의 모든 요소를 처리했으므로 두 번째 배열의 나머지 요소들을 결과 리스트에 추가
answer = [1, 2, 3, 3, 5, 6, 7, 9]
p1 = 3, p2 = 5

 

 

최종 흐름순서도

1. 입력
   n = 3
   a = [1, 3, 5]
   m = 5
   b = [2, 3, 6, 7, 9]

2. 병합
   초기 상태:
   answer = []
   p1 = 0, p2 = 0

   1 < 2 -> answer = [1], p1 = 1, p2 = 0
   3 > 2 -> answer = [1, 2], p1 = 1, p2 = 1
   3 = 3 -> answer = [1, 2, 3], p1 = 1, p2 = 2
   3 < 6 -> answer = [1, 2, 3, 3], p1 = 2, p2 = 2
   5 < 6 -> answer = [1, 2, 3, 3, 5], p1 = 3, p2 = 2

   남은 요소 추가:
   answer = [1, 2, 3, 3, 5, 6, 7, 9]

3. 출력
   1 2 3 3 5 6 7 9