[코딩테스트] 백준 2751 자바

백준 2751

백준 2751 문제

해당 문제는 n의 최댓값이 1,000,000으로 시간 복잡도 O(n2)를 갖는 버블 정렬, 선택 정렬, 삽입 정렬을 사용할 경우에 시간이 초과한다. 따라서 투 포인터 개념을 사용하여 두 그룹을 병합하여 정렬하는 병합 정렬 알고리즘을 사용하여 문제를 풀겠다.

병합 정렬의 시간 복잡도는 O(n log n)이다.

import java.io.*;

public class Boj2751 {

    private static int[] arr, tmp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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++) {
            bw.write(arr[i] + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static void mergeSort(int start, int end) {
        // 종료점이 시작점보다 작거나 같으면 바로 리턴
        if (end - start < 1) {
            return;
        }

        int median = start + (end - start) / 2; // 중간점

        // 재귀 함수 형태로 두 그룹으로 나눠서 병합 정렬 실행
        mergeSort(start, median);
        mergeSort(median + 1, end);

        // 임시 배열에 정렬할 배열의 값 저장
        for (int i = start; i <= end; i++) {
            tmp[i] = arr[i];
        }

        int k = start; // 정렬할 배열의 정렬된 데이터의 인덱스
        int index1 = start; // 왼쪽 그룹의 포인터
        int index2 = median + 1; // 오른쪽 그룹의 포인터

        // 투 포인터 개념을 사용하여 두 그룹을 병합하는 로직
        while (index1 <= median && index2 <= end) {
            // 두 그룹의 포인터가 가리키는 값을 비교하여 더 작은 수를 선택해 정렬할 배열에 저장하고, 선택된 데이터의 포인터를 오른쪽으로 한 칸 이동
            if (tmp[index1] < tmp[index2]) {
                arr[k] = tmp[index1];
                k++;
                index1++;
            } else {
                arr[k] = tmp[index2];
                k++;
                index2++;
            }
        }

        // 한쪽 그룹을 모두 선택한 후에 남은 데이터 저장
        while (index1 <= median) {
            arr[k] = tmp[index1];
            k++;
            index1++;
        }

        while (index2 <= end) {
            arr[k] = tmp[index2];
            k++;
            index2++;
        }
    }
}

풀이

1. 정렬할 배열 arr과 정렬 과정에서 임시로 사용할 임시 배열 tmp를 선언한다.
2. 입력된 데이터를 arr 배열에 저장한다.
3. 병합 정렬을 해주는 메서드 mergeSort()에 배열의 시작 인덱스 0과 마지막 인덱스 n - 1를 인자로 넘겨주어 병합 정렬을 실행한다.
4. mergeSort() 메서드는 종료점 end가 시작점 start보다 작거나 같으면 바로 return한다.
5. 그 외 경우에는 start와 end의 중간점 median을 구한다.
6. median을 기준으로 두 그룹으로 나눠서 mergeSort()로 재귀 함수 형태로 호출하여 두 그룹을 각각 병합 정렬한다.
7. 그럼 정렬된 두 그룹으로 이루어진 배열이 나온다.
8. 해당 배열을 tmp에 저장한다.
9. 정렬할 배열의 정렬된 데이터의 인덱스 k를 start로 저장한다.
10. 왼쪽 그룹의 포인터 index1를 start로 저장한다.
11. 오른쪽 그룹의 포인터 index2를 median + 1로 저장한다.
12. 투 포인터 개념을 사용하여 두 그룹 중 하나의 그룹이 모두 선택될 떄까지 반복한다.
    • 두 그룹의 포인터의 값들을 비교하여 작은 값을 arr 배열에 저장하고 arr의 인덱스와 선택된 그룹의 포인터를 오른쪽으로 이동시킨다.
13. 두 그룹 중 하나의 그룹이 모두 선택됐다면 남은 그룹의 데이터를 저장해준다.