백준 11728번 - 배열 합치기 / Java

문제

https://www.acmicpc.net/problem/11728

11728번: 배열 합치기

머지소트에서 마지막에 배열을 합치는 방식을 구현하는 문제이다. 

양쪽배열에서 앞에꺼부터 차례대로 확인하면서 출력하면 되는문제라 어렵지않았다.

 

알고리즘

1. 왼쪽배열과 오른쪽배열을 탐색할 인덱스번호를 따로 만든다. (left, right)

2. a[left]와b[right]중 작은것을 출력하고 출력한쪽의 인덱스를 1늘린다.

3. 만약 left와 right중 하나라도 최대인덱스에 도달했다면 반복문을 종료하고 최대인덱스에 도달하지 못한 배열을 전부 출력해준다.

소스코드

/*
 * BO11728
 * 2020.02.03
 * Hyeonseong
 */
import java.util.*;    
public class BOJ11728 {
    public static void main(String[] args) {
        Solution s = new Solution();
    }
}
class Solution{
    int n; // 첫번째 배열 크기
    int m; // 두번째 배열 크기
    int a[],b[];
    public Solution() {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        a = new int[n];
        b = new int[m];
        for(int i=0;i<n;i++) {
            a[i] = scan.nextInt();
        }
        for(int i=0;i<m;i++) {
            b[i] = scan.nextInt();
        }
        int left = 0, right =0;
        StringBuilder sb = new StringBuilder();
        while(!(left==n || right==m)) {
            if(a[left]<=b[right]) { // 작은 것을 sb에 저장
                sb.append(a[left]+" ");
                left++;
            } else {
                sb.append(b[right]+" ");
                right++;
            }
        }
        if(left==n) {
            for(int i=right;i<m;i++) {
                sb.append(b[i]+" ");        
            }
        }
        if(right==m) {
            for(int i=left;i<n;i++) {
                sb.append(a[i]+" ");        
            }
        }
        System.out.println(sb.toString().trim());
    }
}