백준 1517번 버블 소트 문제 (Python)

백준 1517번 버블 소트 문제 (Python)

 

백준 1517번 버블 소트 문제를 Python를 사용하여 해결해 보도록 하겠습니다.

 

 

문제

N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

 

입력

첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.

 

출력

첫째 줄에 Swap 횟수를 출력한다

 

예제 입력 / 예제 출력

예제 입력 1	예제 출력 1
3 3 2 1	3

 

 

알고리즘 분류

• 자료 구조
• 정렬
• 세그먼트 트리
• 분할 정복

 

 

작성한 답

코드

시간 초과로 실패한 방식

import sys


def bubble_sort(arr):
    global swap_cnt

    length = len(arr)

    for i in range(length):
        for j in range(0, length - i - 1):
            if arr[j] > arr[j + 1]:
                swap_cnt += 1
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


if __name__ == "__main__":
    swap_cnt = 0
    N = int(sys.stdin.readline())
    ARR = list(map(int, sys.stdin.readline().split()))
    bubble_sort(ARR)
    print(swap_cnt)

 

성공한 방식

import sys

def merge_sort(start, end):
    global swap_cnt, ARR

    if start < end:
        mid = (start + end) // 2
        merge_sort(start, mid)
        merge_sort(mid + 1, end)

        front_idx, back_idx = start, mid + 1
        new_arr = []

        while front_idx <= mid and back_idx <= end:
            if ARR[front_idx] <= ARR[back_idx]:
                new_arr.append(ARR[front_idx])
                front_idx += 1
            else:
                new_arr.append(ARR[back_idx])
                back_idx += 1
                swap_cnt += mid - front_idx + 1

        if front_idx <= mid:
            new_arr = new_arr + ARR[front_idx : mid + 1]
        if back_idx <= end:
            new_arr = new_arr + ARR[back_idx : end + 1]

        for i in range(len(new_arr)):
            ARR[start + i] = new_arr[i]


if __name__ == "__main__":
    swap_cnt = 0
    N = int(sys.stdin.readline())
    ARR = list(map(int, sys.stdin.readline().split()))
    merge_sort(0, N - 1)
    print(swap_cnt)

설명

처음에는 문제의 설명처럼 버블 정렬을 사용하기만 하면 문제를 해결할 수 있는 쉬운 문제로 생각하고 문제를 풀었으나 전혀 아닌 문제였습니다.

실패한 방식에서 보실 수 있듯이 버블 정렬을 사용하면 시간초과가 됩니다.

 

그리하여 생각한 것은 이 문제는 버블 정렬이 아닌 병합 정렬로 해결하는 것입니다.

버블 정렬의 과정을 보면 가장 좌측의 숫자부터 시작해 현재 자리의 숫자가 우측 숫자보다 크면 계속해서 스왑해나가는 방식입니다. 그 과정을 생각해서 병합정렬의 과정에서 우측에 있는 배열에 있는 숫자가 작은 숫자라 앞으로 오게될 때 몇칸이나 이동하는지를 누산해간다면 답을 구할 수 있을 것이라 생각했습니다.

 

예시로 [3, 2, 1, 4]를 정렬하는 예를 들어보겠습니다.

 

 

혹시 그림으로 그린다면 조금이라도 이해가 쉬울까하여 조잡하지만 그려보았습니다.

[3, 2, 1, 4] 를 [3, 2], [1, 4]로, 또 다시 [3], [2], [1], [4] 로 나눈 뒤,

[3], [2] 병합을 시작합니다.

index 0 과 1에 존재하는 3과 2를 병합하면서 뒤쪽 배열이라고 생각할 수 있는 index 1에 있는 2 가 앞쪽 배열이라고 생각할 수 있는 index 0에 있는 3보다 작기 때문에 새로운 배열에 담길 때 기존 자리에서 1칸 이동한 것이 되므로 스왑 1번을 합니다.

그리고 남은 앞쪽 배열에 있는 3은 뒤에 배열에 그대로 넣기만 하면 되기에 스왑 횟수를 증가 시키지 않습니다.

 

[1], [4] 는 이미 정렬이 되어있기에 스왑이 발생하지 않습니다.

 

이제 [2, 3], [1, 4] 를 병합할 때, 뒤쪽 배열이라 생각할 수 있는 index 2에 있는 1 이 앞쪽 배열이라고 생각할 수 있는 index 0에 있는 2 보다 작기 때문에 새로운 배열에 담길 때 기존 자리에서 2칸 이동한 것이 되므로 스왑 2번을 합니다.

그 다음 부터는 앞쪽 배열의 2 와 3, 그리고 뒤쪽에 남아있는 4를 그대로 넣으면 되기에 더이상 스왑이 발생하지 않습니다.

 

이렇게 해서 총 3번의 스왑이 발생하는 것을 확인할 수 있습니다.

 

글과 그림으로서 충분히 이해가 되지 않으실 수 있을 것 같다고 생각합니다.

제가 추천드리는 방법은 제가 작성한 코드를 복사하신 뒤 중간중간에 변경된 배열의 상태와 mid, start, end를 프린트 해보면서 확인하시면 훨씬 이해가 쉬울 것이라 생각됩니다.

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청사항은 언제든지 말씀해주세요!

피드백도 언제나 환영입니다!

 

감사합니다.