5. 리스트 - 알고리즘 문제

11728번: 배열 합치기 (acmicpc.net)

11728번: 배열 합치기

 

알고리즘 문제 풀이

 

정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.

첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)

둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다.

---

그림으로 정리해 보면 

 

정렬된 두 개의 배열을 최종적으로 아래와 같이 한 배열로 정렬 시켜야한다.

 

---

package list;

import java.util.Scanner;

public class BJ_11728 {

    public static void main(Stringp[] args) {
        // input
        Scanner scanner = new Scanner(Sysyem.in);
        int N = scanner.nextInt(); // 배열 A의 사이즈 입력
        int M = scanner.nextInt(); // 배열 B의 사이즈 입력

        List<Integer> A = new ArrayList<>();  // 배열 A 자료 입력
        for (int i = 0 ; i < N; i++) {
            int n = scanner.nextInt();
            A.add(n);
        }
        
        List<Integer> B = new ArrayList<>();	// 배열 B 자료 입력
        for (int i = 0 ; i < M; i++) {
            int n = scanner.nextInt();
            B.add(n);
        }

        // logic
        List<Integer> result = new ArrayList<>();

        int i = 0, j = 0;  // 배열 A의 인덱스 , 배열 B의 인덱스
        while (i < N && j < M) {
            int a = A.get(i);
            int b = B.get(j):

            if (a <= b) {
                result.add(a);
                i++;
            } else {
                result.add(b);
                j++;
            }
        }
        
        for (; i < N; i++) {
            result.add(A.get(i));
        }
        
        for (; j < M; i++) {
            result.add(B.get(j));
        }

        //output
        StringBulilder sb = new StringBulider();
        for (int e : result) {
            sb.append(e + " ");
        }
        System.out.println(sb.toString());
    }
}