[백준/2751] 수 정렬하기 2

Baekjoon Online Judge - 2751

Review

• 병합 정렬로 풀었다.
• 병합 정렬부터 조금 어려워져서 예제를 보고 풀었다.
• 이건 참고한 동영상과 예제. 아직 갈 길이 멀다.

Code (JAVA)

import java.util.*;

public class Main {

  private static void mergeSort(int[] arr) {
    int[] temp = new int[arr.length];
    mergeSort(arr, temp, 0, arr.length - 1);
  }

  private static void mergeSort(int[] arr, int[] temp, int start, int end) {

    //반으로 나눠서
    if(start < end) {
      int mid = (start + end) / 2;

      // 재귀 호출
      mergeSort(arr, temp, start, mid);
      mergeSort(arr, temp, mid + 1, end);

      // 쪼갠 다음에 병합
      merge(arr, temp, start, mid, end);
    }
  }

  private static void merge(int[] arr, int[] temp, int start, int mid, int end) {

    // 임시 배열에 넣음
    for (int i = start; i <= end; i++) {
      temp[i] = arr[i];
    }

    int part1 = start;
    int part2 = mid + 1;
    int index = start;

    // 두 개의 배열을 모두 돌 때까지
    while (part1 <= mid && part2 <= end) {
      // 비교해서 arr에 삽입
      if(temp[part1] <= temp[part2]) {
        arr[index] = temp[part1];
        part1++;
      } else {
        arr[index] = temp[part2];
        part2++;
      }
      index++;
    }

    // 뒤쪽 배열은 비였고, 앞쪽 배열에 데이터가 남아있는 경우
    // 앞쪽 포인터가 배열의 끝에서 남은 만큼을 돌면서
    // 최종적으로 저장할 배열에 남은 값들을 붙여줌
    for(int i = 0; i <= mid-part1; i++) {
      arr[index + i] = temp[part1 + i];
    }
  }

  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];

    for (int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
    }

    mergeSort(arr);

    for (int i = 0; i < n; i++) {
      System.out.println(arr[i]);
    }
    sc.close();
  }

}