[백준]Q2750(수 정렬하기) - JAVA[자바]

1. 문제(URL)

2750번: 수 정렬하기

2. 문제 분류

1. 난이도 : 🥉 브론즈 2

2. 알고리즘 분류 : 정렬, 구현

3. 시간제한 : 1초

3. 문제 분석

1. 1초에 연산할 수 있는 기준은 1억번 이므로 해당 문제는 버블 정렬, 병합 정렬 등 정렬 알고리즘 사용 가능합니다.
     [시간복잡도]
      1) 버블 정렬 = (N)² --> (1,000)²  : 1,000,000 

      2) 병합 정렬 = NlogN --> (1,000)log(1,000) : 약 10,000  

2. 병합 정렬을 연습하기 위해서 병합정렬로 해당 문제를 해결하였습니다.

3. 문제 풀이 순서(예상)
    1) 입력받는 부분 로직 구현
    2) 병합 정렬 수행하는 메서드 구현
         [1] 분할처리 부분 구현

         [2] 병합처리 부분 구현

4. 코드 구현

import java.util.Scanner;

public class Main {

    // 2022-09-24
    // 백준온라인 알고리즘 풀이
    // 백준(BOJ) BRONZE2 수 정렬하기
    // 문제 URL : https://www.acmicpc.net/problem/2750

    static int N;       // 수의 개수
    static int[] arr;   // 수를 담아두는 배열
    static int[] temp;  // 수를 잠시 담아두는 배열

    public static void main(String[] args) {
        // INPUT DATA 정의
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        arr  = new int[N];
        temp = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        // 병합정렬 수행
        mergeSort(0, N-1);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(arr[i]).append("\n");
        }
        System.out.println(sb.toString());
    }

    // 병합정렬 수행 메서드
    private static void mergeSort(int start, int end) {
        // 병합정렬 수행 조건
        if (start < end) {
            // 1. 분할처리
            int mid = (start + end) / 2;
            mergeSort(start, mid);
            mergeSort(mid+1, end);

            // 2. 병합처리
            mergeNum(start, end, mid);
        }
    }

    private static void mergeNum(int start, int end, int mid) {
        // 왼쪽부분 시작 변수
        int i = start;
        // 오른쪽부분 시작변수
        int j = mid +1;
        // 임시 배열 시작변수
        int k = start;
        // 오름차순으로 정렬
        while (i <= mid && j <= end) {
            if (arr[i] > arr[j]) {
                temp[k] = arr[j];
                j++;
            } else {
                temp[k] = arr[i];
                i++;
            }
            k++;
        }

        // 남은 값 일괄 복사
        while (i <= mid) {
            temp[k] = arr[i];
            i++;
            k++;
        }

        while (j <= end) {
            temp[k] = arr[j];
            j++;
            k++;
        }

        // 정렬한 값 원래 배열에 옮기는 작업
        for (int n = start; n <= end; n++) {
            arr[n] = temp[n];
        }
    }
}

 

GITHUB 소스 : 바로가기

 

Reference.

백준 온라인 저지 (https://www.acmicpc.net/)