[JAVA][Baekjoon] 2751번 수 정렬하기 2 🌟🌟🌟

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

 

📌 접근 방식

병합 정렬을 사용해 풀어보았습니다.

[알고리즘] 병합 정렬(Merge Sort)이란?

 

1️⃣ 배열 나누기:
주어진 배열을 반으로 나누고, 또 나누고... 이렇게 가장 작은 단위(원소 1개)가 될 때까지 나누고

 

2️⃣ 정렬하며 합치기:
작은 단위로 나눈 배열들을 다시 하나씩 합치면서 정렬한다. 

 

3️⃣ 완성된 배열 반환:
마지막에 모든 배열이 합쳐지면 정렬된 결과가 완성!!!

병합정렬의 핵심은 재귀와 합치는 과정에서의 정렬인 것 같다

데이터를 직접 나누는 게 아니라 인덱스 범위를 조정하면서(투포인터 처럼) 작업하기 때문에 메모리를 효율적으로 사용할 수 있던 것 같다!!!

 

✅ PASS CODE

import java.io.*;

public class Main {
    public static int[] arr, tmp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        tmp = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        mergeSort(0, N-1);
        for (int i = 0; i < N; i++) {
            System.out.println(arr[i]);
        }
    }
    public static void mergeSort(int s, int e) {
        if(e-s < 1) return;
        int m = (s+e)/2;

        mergeSort(s, m);
        mergeSort(m+1, e);
        for(int i = s; i <= e; i++) {
            tmp[i] = arr[i];
        }
        int index1 = s;
        int index2 = m+1;
        int k = s;
        while(index1 <= m && index2 <= e) {
            if(tmp[index1] > tmp[index2]) {
                arr[k] = tmp[index2];
                index2 ++;
                k++;
            } else {
                arr[k] = tmp[index1];
                index1 ++;
                k++;
            }
        }
        while(index1 <= m) {
            arr[k] = tmp[index1];
            index1 ++;
            k++;
        }
        while(index2 <= e) {
            arr[k] = tmp[index2];
            index2 ++;
            k++;
        }
    }
}

 

🤔 느낀 점

처음에는 병합정렬이라는 알고리즘이 생소해서 반복문을 사용해야하는지 재귀를 사용해야하는지 고민이 많았다..

보통 이런 정렬 문제에서는 재귀를 사용하는게 효율적인 것 같다.

기존에는 정렬하면 Arrays.sort() 같은 내장 함수를 많이 사용했는데, 직접 구현하니 정렬의 내부 구조를 이해할 수 있었고, 상황에 따라 어떤 정렬이 효율적인지 생각해보게 되는 것 같다.

병합정렬은 시간 복잡도가 O(N log N)라 데이터가 많아도 안정적으로 처리할 수 있는 것 같다. 아직은 재귀로 문제를 푸는 것이 헷갈리고 어려워서 더 연습이 필요할 것 같다!💡🔥