알고리즘 풀이 - 백준 11728(배열 합치기, 분할정복)

 

관련글

 

분할정복 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

정렬된 두 배열 A, B를 합치고 정렬해서 출력하는 문제

 

2. 풀이

 

이 문제는 정렬된 두 배열을 합치는 것이므로 단순히 병합 정렬 중 병합을 진행하는 문제이다.

병합 정렬 관련된 내용은 여기를 참조하고 단순한 문제이니 바로 코드를 통해 이해하자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 각 배열을 입력받는다.
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        int[] a = new int[A];
        int[] b = new int[B];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i < A; i++){
            a[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for(int i=0; i < B; i++){
            b[i] = Integer.parseInt(st.nextToken());
        }

        // 입력 받은 배열을 순서대로 StringBuilder에 추가한다.
        int i=0;
        int j=0;
        StringBuilder sb = new StringBuilder();
        while(i < A && j < B){
            sb.append(a[i] <= b[j] ? a[i++] : b[j++]).append(" ");
        }
        
        // 아직 남아 있는 내역이 있을 수 있으므로 추가
        while(i < A) sb.append(a[i++]).append(" ");
        while(j < B) sb.append(b[j++]).append(" ");
        System.out.println(sb); // 출력
        br.close();
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.