[백준] 1517 버블 소트 - 파이썬

풀이.

세그먼트 트리로는 아직 풀지 못해서 병합정렬로 풀었다.

우선 문제의 버블 정렬은

두 요소 간 순서가 맞으면 가만히 놔두고 순서가 틀렸다면 숫자를 교환해야한다. 그리고 swqp의 횟수를 구해야한다.

병합 정렬을 이용하여 swap의 횟수를 구하였다.

 

소스코드.

 

	# 병합 정렬 풀이
	import sys
	def mergeSort(start, end):
	global count
	if start < end:
	mid = (start + end) // 2
	mergeSort(start, mid)
	mergeSort(mid+1, end)
	left = start
	right = mid + 1
	tmp = []
	while left <= mid and right <= end:
	if arr[left] <= arr[right]:
	tmp.append(arr[left])
	left += 1
	else:
	tmp.append(arr[right])
	right += 1
	count += (mid - left + 1)
	if left <= mid:
	tmp += arr[left:mid+1]
	if right <= end:
	tmp += arr[right:end+1]
	for i in range(len(tmp)):
	arr[start + i] = tmp[i]
	input = sys.stdin.readline
	count = 0
	n = int(input())
	arr = list(map(int, input().split()))
	mergeSort(0, n-1)
	print(count)

view raw 1517 - 버블 소팅(mergeSort).py hosted with ❤ by GitHub