백준 - 1517번 버블 소트

출처 : 1517번: 버블 소트 (acmicpc.net)

1517번: 버블 소트

---

버블 소트 성공분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

512 MB

11536

2851

1904

28.632%

문제

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 복사

3

3 2 1

예제 출력 1 복사

3

 

---

[ 문제 설명 ]

 

버블 소트 : 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

왼쪽에서 오른쪽으로 정렬하면 가장 큰 수가 오른쪽으로 갈 테니까

마지막 부분을 빼는 식으로 n - 1번 다시 반복.

 

=> 문제는 버블 소트인데 버블 소트로 구현하면 시간 초과 발생!!

 

# 시간 초과 발생한 코드

 

import sys


def bubble_sort(arr):
    global cnt
    end = len(arr) - 1
    while end > 0:
        last_swap = 0
        for i in range(end):
            if arr[i] > arr[i + 1]:
                cnt += 1
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                last_swap = i
        end = last_swap


n = int(input())
l1 = list(map(int, sys.stdin.readline().split()))
cnt = 0
# print(l1)
bubble_sort(l1)
print(l1)
print(cnt)

그럼 무엇으로 해야 할까??

 

여러 방법으로 문제를 풀 수 있지만 저는 병합 정렬로 문제를 풀려고 합니다.

 

그림 1 - 병합 정렬을 이용하려는 원리 설명

이 그림은 병합정렬 개념 자체는 설명이 부족한데, 글로 설명하면 그림처럼 반으로 계속 찢다가 다시 합치면서 하나하나 씩 정렬하는 방법이라고 생각하시면 됩니다.

 

---

[ 코드 ]

 

import sys

input = sys.stdin.readline


def merge(left, right):
    global cnt
    # left, right = len(left), len(right)
    i, j = 0, 0
    temp = []
    while i < len(left) and j < len(right):

        if left[i] > right[j]:
            temp.append(right[j])
            j += 1
            cnt += len(left) - i  # 왼쪽과 오른쪽을 비교했을 때 만약 오른쪽이 왼쪽보다 작다면,
            # 왼쪽의 남은 확인하지않은 인덱스들은 오른쪽보다는 당연히 큰 값으로 남아있으므로
            # 그 수만큼 갯수를 더해주면 됩니다.

        else:
            temp.append(left[i])
            i += 1

    if i == len(left):
        temp.extend(right[j:])
    else:
        temp.extend(left[i:])
    return temp


def merge_sort(list):
    if len(list) <= 1:
        return list
    else:
        mid = len(list) // 2
        left = merge_sort(list[: mid])
        right = merge_sort(list[mid:])
        return merge(left, right)


n = int(input())
cnt = 0
arr = list(map(int, input().split()))
arr = merge_sort(arr)
print(arr)
print(cnt)

 

 

 

---

후기

 

진짜진짝 복습은 할수록 그 부분에 대해서

좀 더 깊은 이해가 되는 것 같아서

무조건적으로 필요한 거 같다.