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

백준 1517

백준 1517 문제

해당 문제는 버블 정렬을 할 때의 swap이 몇 번이 발생하는지 알아내는 문제이지만, n의 최댓값이 500,000으로 시간 복잡도가 O(n2)인 버블 정렬을 사용할 경우에 시간이 초과된다.

따라서, 시간 복잡도가 O(n log n)인 병합 정렬을 사용하여 정렬을 해야 한다. 그럼 병합 정렬을 하면서 어떻게 swap이 몇 번이 발생하는지 알아야하는데, 병합 정렬은 정렬된 왼쪽 그룹과 오른쪽 그룹의 포인터가 가르키는 값을 비교하여 더 작은 수를 정렬할 배열에 넣으면서 정렬을 한다. 만약 오른쪽 그룹의 포인터 값이 왼쪽 그룹의 포인터 값보다 작을 경우에 선택된 값은 왼쪽 그룹에 남은 값들을 모두 swap하며 이동한 것이나 다름 없다.

정리하자면, 왼쪽 그룹의 포인터 값이 선택될 때, 왼쪽 그룹의 남은 데이터의 수를 result에 더해주면 swap이 몇 번 발생했는지 알 수 있다.

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

public class Boj1517 {

    private static int[] arr, tmp;
    private static long result;

    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]; // 임시 배열 선언
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken()); // 정렬할 배열에 데이터 저장
        }

        mergeSort(0, n - 1); // 병합 정렬 실행

        // 결괏값 출력
        System.out.println(result);

        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[index2];
                result = result + index2 - k; // 오른쪽 그룹 데이터 값이 더 작아 선택될 때 swap이 일어났다고 가정하고, 현재 남아 있는 왼쪽 그룹 데이터 개수만큼 결괏값에 더함
                k++;
                index2++;
            } else {
                arr[k] = tmp[index1];
                k++;
                index1++;
            }
        }

        // 한쪽 그룹을 모두 선택한 후에 남은 데이터 저장
        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의 인덱스와 선택된 그룹의 포인터를 오른쪽으로 이동시킨다.
      • 오른쪽 그룹 데이터 값이 더 작아 선택될 때 swap이 일어났다고 가정하고, 현재 남아 있는 왼쪽 그룹 데이터 개수만큼 결괏값에 더한다.
13. 두 그룹 중 하나의 그룹이 모두 선택됐다면 남은 그룹의 데이터를 저장해준다.
14. result를 출력한다.