[백준/파이썬] 1517번 버블 소트 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1517번 버블 소트
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

주어진 수열을 버블 정렬할 때 발생하는 교환 횟수를 구하는 문제입니다.

코드

import sys

n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))

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

wow = 0
def merge(start, mid, end):
    global wow
    cnt = 0
    first_i = start
    second_i = mid+1
    tmp = []
    while first_i <= mid or second_i <= end:
        if first_i <= mid and (second_i > end or\
                              nums[first_i] <= nums[second_i]):
            tmp.append(nums[first_i])
            first_i += 1
            wow += cnt
        else:
            tmp.append(nums[second_i])
            second_i += 1
            cnt += 1
    for i in range(end-start+1):
        nums[start+i] = tmp[i]

merge_sort(0, n-1)
print(wow)

설명

병합 정렬 과정에서 오른쪽 원소가 먼저 나올 때마다 역전 수를 세면 버블 정렬의 교환 횟수와 동일합니다.

---

• 백준 문제풀이 전체 목록 보기

---