백준 1517 - 버블소트

문제

풀이

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

public class Q1517_버블소트 {

    public static int[] arr;
    public static int[] tmp;
    // int로 선언하니 에러 발생
    // swap 횟수를 누적할 변수
    public static long result;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
		
        // 정답 배열을 저장할 변수
        arr = new int[n + 1];
        // 임시 배열로 활용
        tmp = new int[n + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        result = 0;
        
        // 병합 정렬 호출
        merge(1, n);
        System.out.println(result);
    }

    public static void merge(int s, int e) {
    	// 최소구간으로 배열을 쪼갰다면 재귀함수를 빠져나와 다음 연산을 진행
        if (e - s < 1) {
            return;
        }
		
        // 각 구간의 중간 인덱스를 나타낼 변수
        int mid = s + (e-s)/2;

		// 배열을 최소구간으로 쪼개서 정렬을 진행하기 위해 재귀호출 수행
        merge(s, mid);
        merge(mid + 1, e);
		
        // 쪼개진 각 구간의 시작점부터 1씩 증가할 변수
        int point = s;
        
        // 2개의 구간중 첫번째 구간의 시작점
        int idx1 = s;
        // 2개의 구간중 두번재 구간의 시작점
        int idx2 = mid + 1;
		
        
        // 연산을 위해 임시로 사용할 배열 초기화
        for (int i = s; i<=e; i++){
            tmp[i] = arr[i];
        }
		
        
        // 각 구간중 한쪽 구간이 정렬 완료될 때까지 반복문 수행
        while (idx1 <= mid && idx2 <= e) {
        	// 실제로 버블정렬에서 순서가 바뀌는 경우는 왼쪽에 있는 값(idx1)이 오른쪽에 있는 값(idx2)
            // 보다 클 때 swap이 일어나므로 이 경우에만 result에 이동횟수를 누적해주자
            if (tmp[idx1] > tmp[idx2]){
                arr[point] = tmp[idx2];
                // 이동값을 구해 결과에 누적
                result = result + idx2 - point;
                point++;
                idx2++;
            // 왼쪽값이 더 작다는 말은 버블소트에서 정렬을 하지 않는다는 것이므로
            // 결과에 누적하지 않고 정렬만 진행
            }else{
                arr[point] = tmp[idx1];
                point++;
                idx1++;
            }
        }
		// 아래 두개의 반복문 또한 swap이 일어나지 않으므로 정렬만 진행
        while (idx1 <= mid) {
            arr[point] = tmp[idx1];
            point++;
            idx1++;
        }
        while (idx2 <= e) {
            arr[point] = tmp[idx2];
            point++;
            idx2++;
        }
    }
}

리뷰

• 문제 제목은 버블소트였는데 값의 범위를 보니 버블소트를 사용하면 시간초과가 뜨는 문제였다.
  그래서 처음에는 버블소트프로그램 문제 풀이처럼 Arrays.sort를 이용해 정렬을 하고, 정렬하기 전과 후의 인덱스 차이가 가장 큰 값을 구하면 되나? 싶었다.
  그런데 이 방법은 정렬이 몇번째 루프에서 완료가 되는지 알아내는 방법이었고, 이 문제는 swap이 몇번 일어나는지 알아내는 문제로 다른 방법으로 문제를 풀어야 했다.
  결국 이 문제는 병합정렬을 이용해 풀어야 하는 문제였다. 제목은 버블소트라면서ㅡㅡ

• 여기서 배열의 범위를 n+1로 지정한 이유는 단순히 연산에 있어서 편하게 진행하려고 설정한 값이다.

• 병합 정렬을 이용해 푸는 이유는 퀵정렬의 경우 원래의 순서는 완전히 무시하고 pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하는 특성 때문에 그렇다고 한다.

• 지난 문제를 정리하면서 병합정렬에 대해 기본적으로 정리를 끝냈다고 생각했는데, 실제로 swap이 이뤄지는 부분을 설정하는 부분에서 많이 헷갈렸다. 응용부분까지는 아직 갈길이 먼 것 같다ㅜㅜ