[백준] 11728번 배열 합치기 Merge Sort 풀이법 : Programming Story

1. 문제

www.acmicpc.net/problem/11728

문제는 위의 링크에 들어가면 확인할 수 있다.

2. merge sort

merge sort 중에서 합치는 부분을 코드로 구현해야 하는 문제이다.

Merge Sort에 관한 내용은 이전 포스팅에서 정말 자세하게 다루었다.

https://www.programmingstory.com/2024/02/merge-sort.html

위의 포스팅에서 합치는 코드 또한 다루었기 때문에 한번 읽어보면 이 문제를 푸는데에도 큰 도움이 될 것이다.

3. 풀이

다른 점은 위 포스팅에서는 start, end 라고 해서 두 그룹을 합쳐서 처음과 끝 index를 따로 표시해주었는데 이번에는 두 배열을 서로 다른 배열로 입력받아놓았다는 점이다.

그래도 알고리즘 자체는 완전히 같다.

합치는 코드 부분만 우선 살펴보겠다.

 //합치는 코드
        int i=0; //첫번째 그룹 index
        int j=0; //두번째 그룹 index
        int k=0; //현재 저장하는 c index
        while(i<n && j<m){
            if (a[i]<=b[j]){
                c[k++]=a[i++];
            }
            else {
                c[k++]=b[j++];
            }
        }
        while(i<n){
            c[k++]=a[i++];
        }
        while(j<m){
            c[k++]=b[j++];
        }

여기서 c라는 배열에다가 정렬된 것을 저장해놓을 것이고, 두 그룹의 index별로 대소관계를 비교해 먼저 c 배열에 들어와야 할 요소를 판단한다.

마지막에 while문은 만약 하나의 그룹의 원소들은 모두 다 c 배열에 저장이 되었는데 다른 그룹의 원소들이 남아있을 경우를 대비하여 c 배열에 순서대로 저장하는 코드를 추가한 것이다.

4. 전체 코드

입력받고 출력하는 것까지 전체 코드는 아래와 같다.

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.valueOf(line[0]);
        int m = Integer.valueOf(line[1]);
        int[] a = new int[n];
        line = br.readLine().split(" ");
        for (int i=0; i<n; i++) {
            a[i] = Integer.valueOf(line[i]);
        }
        int[] b = new int[m];
        line = br.readLine().split(" ");
        for (int i=0; i<m; i++) {
            b[i] = Integer.valueOf(line[i]);
        }
        int[] c = new int[n+m]; //저장할 공간
        
        //합치는 코드
        int i=0; //첫번째 그룹 index
        int j=0; //두번째 그룹 index
        int k=0; //현재 저장하는 c index
        while(i<n && j<m){
            if (a[i]<=b[j]){
                c[k++]=a[i++];
            }
            else {
                c[k++]=b[j++];
            }
        }
        while(i<n){
            c[k++]=a[i++];
        }
        while(j<m){
            c[k++]=b[j++];
        }
        StringBuilder sb = new StringBuilder();
        for (int in=0; in<n+m; in++) {
            sb.append(c[in] + " ");
        }
        System.out.println(sb);
    }
}

입력이 많기 때문에 Scanner 를 사용하는 대신 BufferedReader를 사용했고, 출력또한 매번 System.out.print()를 사용하는 것이 아닌, StringBuilder를 사용해서 한꺼번에 출력하여 시간을 줄였다.