[백준] 1517번 : 버블 소트 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1517번: 버블 소트

 

1. 문제 설명

2. 풀이과정

해당 문제의 제목은 버블 소트이지만 N의 최대 범위가 500,000이므로 버블 정렬을 사용하면 제한 시간을 초과하게 된다.

하여 해당 문제는 버블 정렬이 아닌 O(nlogn) 시간 복잡도를 가지는 병합 정렬을 사용해야 한다.

병합 정렬에서 두 그룹을 병합하는 과정에 버블 정렬의 swap이 포함되어 있으므로 병합 정렬을 사용해 문제를 풀어도 문제의 정답인 swap 횟수를 구할 수 있다.

병합 정렬로 정렬을 하는 과정에서 index가 이동한 거리 즉, swap 횟수를 result 변수에 저장한다.

 

슈도코드

1. N(정렬할 수 개수) 입력받기
2. A(정렬할 리스트 선언) 입력받기
3. temp(정렬할 때 잠시 사용할 임시 리스트 선언)
4. result(swap 횟수 저장할 변수)
5. 병합 정렬(s, e):
   1. m(중간점) 구하기
   2. 병합 정렬(s, m)
   3. 병합 정렬(m + 1, e)
   4. for s ~ e: temp 리스트 저장
   5. 두 그룹 병합
      1. index1(앞쪽 그룹 시작점)
      2. index2(뒤쪽 그룹 시작점)
      3. while (index1 <= 중간점) and (index2 <= 종료점):
      4. 양쪽 그룹의 index가 가리키는 값을 비교한 후
      5. 더 작은 수를 선택해 리스트에 저장하고
      6. 선택된 데이터의 index값을 오른쪽으로 한 칸 이동
      7. 만약 뒤쪽 데이터 값이 더 작아 선택되면 swap이 일어난 것과 동일 (swap 횟수 증가)
      8. 반복문이 끝난 후 남아 있는 데이터 정리
6. 병합 정렬 함수 수행
7. 결괏값 출력

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

temp = [0] * N
result = 0

def merge_sort(s, e):
    global result

    if (e - s < 1):
        return
    
    m = int(s + (e - s) / 2)
    merge_sort(s, m)
    merge_sort(m + 1, e)

    for i in range(s, e + 1):
        temp[i] = A[i]

    k = s
    index1 = s
    index2 = m + 1
    while (index1 <= m) and (index2 <= e):
        if (temp[index1] > temp[index2]):
            A[k] = temp[index2]
            result += index2 - k
            k += 1
            index2 += 1
        else:
            A[k] = temp[index1]
            k += 1
            index1 += 1

    while (index1 <= m):
        A[k] = temp[index1]
        k += 1
        index1 += 1

    while (index2 <= e):
        A[k] = temp[index2]
        k += 1
        index2 += 1

merge_sort(0, N - 1)
print(result)