[백준] 1517 버블 소트 java 풀이 (그림으로 쉽게 이해하기)

1. 문제 설명 📌

문제 링크

1차원 배열이 주어지고, 해당 배열을 버블 정렬로 정렬한다고 했을때, 전체 과정 중에서 swap은 몇 번 일어났는지 구하라.

2. 접근 방식 🗃️

Key Word: Merge_sort, Two Pointer

• 분할 정복, 투 포인터를 활용해 입력에 대해 병합 정렬을 실행한다.
• 매 재귀 순간마다 정렬이 될텐데, 이때 자리 바꿈이 일어난 횟수를 센다.
• 위의 과정에서 구한 자리 바꿈 횟수를 누적해 출력한다.

전체 과정을 간략히 설명하면 다음과 같다.

(1) 지금부터 병합 정렬이 무엇인지,

(2) 버블 정렬로 정렬하라 했는데 왜 병합 정렬을 사용하고 그것이 통하는지,

(3) 어떻게 구현하면 되는지

세세하게 설명하겠다.

(1) 병합 정렬이 무엇인지

병합정렬은 분할 정복과 투 포인터를 활용해 값들을 정렬하는 알고리즘이다. 여기선 간단히 설명하고 넘어가겠다. 자세히 알고 싶은 분은 병합 정렬 - geeksforgeeks에 자세히 설명되어 있으니 참고하기 바란다.

병합 정렬은 다음과 같은 순서로 구분되어 있다.

• 정렬해야할 값들을 더 이상 쪼갤 수 없을 때까지 분할한다. (분할 by 재귀)
• 분할된 값들을 인접한 그룹과 대소관계를 비교하여 정렬 되도록 합친다. (정복 by 투 포인터)

다음은 비 정렬된 배열을 병합 정렬을 이용해 오름차순으로 정렬하는 과정을 보면서 병합 정렬을 이해해보자.

a. 분할 by 재귀

재귀를 통해, 모든 값을 더 이상 쪼갤 수 없을 때까지 나눈다. 해당 방식은 완성된 전체 ➜ 개별 개체가 되므로 top-down 방식이다. 정복은 bottom-up 방식이다.

b. 정복 by 투 포인터

첫 정복 과정부터 작성해보았다. 우리는 오름차순 정렬을 목표로 하고 있음으로, 두 숫자의 대소 관계를 비교하고 적절히 위치를 바꾼다. 이런 식으로 작은 덩어리를 합쳐나가면 결국에는 오름차순 정렬이 될 것이다. 이렇게 작은 과정의 반복으로 전체를 변화시키는 것을 분할 정복이라고 한다. 그럼 여기서 투 포인터는 어떻게 쓰였을까? 위의 첫 예시는 1:1 비교라서 투 포인터가 꼭 필요하지 않지만 다음과 같이 그룹과 그룹 간의 비교라면 필요해진다.

 

그룹간의 대소관계를 비교하기 위해서 L 포인터와 R 포인터를 만들었다. 두 포인터가 가리키는 값을 비교하여 작은 값 순으로 E 포인터에 들어가게 된다. 사용한 포인터는 다음 숫자를 가리키도록 한다.

 

1과 5를 비교했을 때, 1이 작음으로 합친 배열의 앞칸을 채운다. 이후 R포인터는 앞으로 움직이고, E도 값이 찼으니, 한 칸 앞으로 전진해야 한다. 이런식으로 하면,

 

이렇게 정렬될 것이다. 전체 정렬 과정을 살펴보면,

 

이렇게 될 것이다. 병합 정렬을 이해했으니 다음으로 넘어가자.

(2) 왜 병합 정렬을 사용하고 그것이 통하는가?

a. 왜 병합 정렬 사용?

버블 정렬은 시간 복잡도가 O(\(N^{2})\) 이라 N <= 500,000인 문제의 조건상 시간 초과가 난다. 반면, 병합 정렬은 성질이 버블 정렬과 유사하면서도 시간 복잡도는 O(NlogN)이 들어 시간 안에 문제를 풀 수 있다.

 

둘 사이의 어떤 점이 유사할까?

공통점은 다음과 같다.

• 각 원소가 대소관계 비교를 통해 자리를 이동한다.
• 반복문 마다 각 원소가 얼마나 움직였는지 확인이 가능하다

위의 예시로 쓴 7 2 4 6 5 3 1을 버블 정렬로 정렬하고, 그때마다 몇 번의 swap이 있었는지 체크해보겠다.

 

 

위와 같이, 매 반복문마다 몇 번의 움직임이 있었는지 확인 가능하다. 차이점이 있다면 버블 정렬의 경우 한 반복문에서 하나의 수만 움직인다. 반면 병합 정렬은 하나의 재귀에서 여러 수가 동시에 움직인다.이다.

b. 왜 병합 정렬이 통함?

둘의 작동방식은 달라도 원소 간의 자리를 교체하는 기준과 매 순간 움직임 횟수를 셀 수 있다는 성질이 같기에 , 총합만 구하면 되는 우리 입장에서는 *속도가 빠른 병합 정렬을 활용해 * 총합만 구하면 되는 것이다.

그래서 어떻게 구현하면 됨?

a. swap 했다.의 기준을 잡아야 한다.

버블 정렬 예시의 Loop 1을 봐도 Swap을 세는 시각에 따라 '7이 오른쪽으로 6번 swap 했다.' 와 '1,2,3,4,5,6이 왼쪽으로 각각 1번씩 swap했다.' 두가지 시각에서 볼 수 있기 때문이다. 많은 풀이에서 후자를 선택했지만, 필자의 경우 그것이 직관적이지 않아서, 전자를 택했다. 따라서 이번 풀이에서는 숫자의 오른쪽 이동을 swap의 기준으로 잡겠다.
(예시 - 7이 6번 오른쪽으로 이동 == 7이 6번 swap)

b. 항상 원소가 이전 위치에서 얼마나 움직였는지로 swap 횟수를 체크해야 한다.

많은 사람들이 원소의 최초 위치에서 각 재귀마다 원소가 얼마나 움직였는지를 체크하는 실수를 한다. 위 버블 정렬의 예시를 봐라. 6은 실제로 3번 이동했지만, 최초 위치와 비교하면 2번밖에 움직이지 않았다. 이는 뒤에 있던 수가 앞으로 오면서 그 여파로 모든 수의 위치가 달라졌기 때문이다.
원소 별 이전 위치 기억을 위해 Node Class를 만들고 해당 객체에 이전 위치(prev_index)와 값(v)을 저장하겠다. 그리고 이전 위치와 비교해 오른쪽으로 옮겨졌으면 그 갭차를 swap_cnt에 더하면 된다.

 

 

위의 그림에서 가로축을 하나의 재귀로 보았을 때, 오른쪽으로 이동한 값과 이동 전과의 격차를 기록하였다.

3. 코드 소개 🔎

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


public class Main {
    /*
    * 병합정렬은 버블정렬과 마찬가지로 인접한 원소들간의 대소관계를 비교 후 위치를 변경한다.
    * 병합정렬을 이용해 버블정렬의 swap 횟수를 세는 것은, 병합 정렬을 진행하는 매 회차마다,
    * 원소들이 얼마나 왼쪽에서 오른쪽으로 움직였는지, 그 횟수를 세어주면 된다.
    *
    * 따라서 Node라는 Class를 만든다. 해당 Node는 이전 index와 value를 저장한다.
    * 현 index - 이전 index가 양수인 경우 왼쪽에서 오른쪽으로 이동한 것임으로, 그 차이를 swap_cnt에 세어준다.
    * */

    static int N;
    static long swap_cnt = 0;
    static Node [] arr;
    static Node [] temp;
    public static void main(String[] args) throws IOException {
        // 1. 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N       = Integer.parseInt(br.readLine());
        arr     = new Node[N];
        temp    = new Node[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = new Node(i, Integer.parseInt(st.nextToken()));
        }
        // 2. 계산
        merge_sort(0, N-1);
        // 3. 출력
        System.out.println(swap_cnt);
    }

    public static void merge_sort(int start, int end){
        // 0. 기저 조건
        if(start == end) return;
        // 1. 재귀
        int mid = (start+end)/2;
        merge_sort(start, mid);
        merge_sort(mid+1, end);
        // 2. 계산
        //  (1) 임시로 값을 저장하는 배열 temp에 값 집어넣기
        for(int i = start; i <= end; i++){
            temp[i] = arr[i];
        }
        //  (2) while문과 포인터를 활용한 정렬
        int E = start; int L = start; int R = mid+1;
        while (L <= mid && R <= end){
            // a. 대소관계 비교 후 적절한 위치에 넣어주기
            if(temp[L].v > temp[R].v){
                arr[E] = temp[R++];
            }else {
                arr[E] = temp[L++];
                // 앞으로 전진했다면 swap 진행한 것임으로, 해당 갭차를 swap_cnt에 더해주기
                if(arr[E].prev_idx < E) swap_cnt += E - (long) arr[E].prev_idx;

            }
            // 모두 현재 index를 이전 index로 넣어주기
            arr[E].prev_idx = E;
            E++;
        }
        //  (3) 정렬 후 남은 값들 다시 집어넣어주기
        if(L <= mid){
            while (L <= mid){
                arr[E] = temp[L++];
                if(arr[E].prev_idx < E) swap_cnt += E - (long)arr[E].prev_idx;
                arr[E].prev_idx = E;
                E++;
            }
        }
    }
}

class Node {
    int prev_idx;
    int v;

    public Node (int prev_idx, int v) {
        this.prev_idx = prev_idx;
        this.v = v;
    }
}

 

2번 계산의 (3) 남은 투 포인터 정렬 후 아직 남은 값들을 배열에 차례대로 넣기에서 R 포인터 그룹에서도 남는 게 있을텐데 따로 전체 배열인 arr에 넣지 않고 있다. 그 이유는 이미 전체 배열 arr가 mid값을 기준으로 정렬이 된 상태다. R 포인터 그룹에 값이 남아있다면 다른 수들보다 커서 자기 자리 그대로 지킨 경우를 뜻한다. 따라서 정렬을 따로 해줄 필요 없이 정렬되어 있다.

4. 배운 것들 🎯

저번에 풀 땐 혼자 풀었던 것 같은데, 이번엔 다른 사람들의 풀이와 내 이전 답안을 참고했다. 이전 풀이가 더 깔끔한 것에 좌절했다... 로스트 테크놀로지가 이론 상 가능한가 싶었지만 가능하구나...