버블정렬과 합병정렬을 완전히 이해한다면 (#1517)

 

#1517 버블 소트 https://www.acmicpc.net/problem/1517

 

 

버블정렬에서 발생하는 swap의 횟수를 구하는 알고리즘이다.

 

개념을 간단히 설명하면

 

버블 정렬은, 옆 인덱스와 크기를 비교해서 값의 위치를 찾아가는 형태의 정렬방법이다.

따라서, 옆 인덱스와 값을 교환하는 swap이라는 행위가 발생한다.

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog

반만 합병정렬은 분할정복의 접근법으로 정렬을 진행하는 방법이다.

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

 

 

이 문제의 핵심은

버블정렬의 시간복잡도는 O(n^2)

합병정렬의 시간복잡도는 O(nlogn) 이라는 사실을 기억하고 해결하는 것이다.

 

버블 정렬의 swap 횟수를 구하는 문제이지만, 버블정렬을 사용해 풀이하면 시간초과가 발생한다.

따라서 합병정렬을 이용해 정렬을 진행하고, 그 과정에서 swap 횟수를 계산하는 아이디어가 필요하다.

 

다른 분들의 코드를 참조하여 힘겹게 구현했다.

 

import sys
input = sys.stdin.readline
n = int(input())
nums = list(map(int, input().split()))
answer = 0

def merge_sort(s, e):
    global answer
    # 재귀 종료 조건
    if e-s <1:
        return
    
    # divide
    m = (e+s)//2
    merge_sort(s, m)
    merge_sort(m+1, e)

    # conquar
    tmp = []
    # tmp 추적 투포인터
    i, j = s, m+1
    # 두 그룹을 비교하며 저장
    while i<=m and j <=e:
        # swap count의 방향을 잘 잡아야한다.
        if nums[i] > nums[j]: # 뒤쪽에 있는 작은 숫자가 앞으로 이동하는 경우
            tmp.append(nums[j])
            # 인덱스를 증가하기 전에 swap 횟수 계산하기
            answer += m-i+1
            j+=1
        else:
            tmp.append(nums[i])
            i+=1
    # 왼쪽 그룹이 남은 경우
    if i<=m:
        tmp = tmp + nums[i:m+1]
    # 오른쪽 그룹이 남은 경우
    if j<=e:
        tmp = tmp + nums[j:e+1]

    # 복사하기
    for i in range(len(tmp)):
        nums[s+i] = tmp[i]
merge_sort(0, n-1)
# print(nums)
print(answer)

 

 

합병정렬을 구현할 때

기존 리스트와 정렬을 진행할 리스트를 이중으로 구현하는 것이 중요하다.

하지만 메모리 사용을 최소화 하는 방법으로 구현할 필요가 있다.

 

tmp를 만들어서 정렬한 값을 저장하고

이를 함수 맨 마지막 부분에서 복사하는 과정을 보자.

 

재귀적으로 원본 리스트의 일부를 정렬하는데, 딱 그 일부분만 반영하는 모습을 볼 수 있다.

이렇게 하면 메모리 사용랑과 실행 시간을 줄일 수 있다.