백준 11728 : 배열 합치기(feat. Tim sort)

https://www.acmicpc.net/problem/11728

11728번: 배열 합치기

 

해결 방법 : merge sort

• 문제에 주어진 두 배열이 정렬되어 있기 때문에 가장 앞에 있는 요소끼리 비교하여 추가하면 된다.
• 정렬을 위한 비교 연산만 생각하면 O(N + M)으로 해결된다.

 

• 문제가 너무 단순해서 시간초과가 까다로운지 보려고 sorted(arr1 + arr2)로 제출해봤는데, 오히려 조금 더 빠르다. 리스트를 합치는데 M, 전체를 정렬하는데 (N+M)log(N+M)인데 왜 이런 결과가 나올까?
  • python의 sort 내장함수가 어떻게 돌아가는지 찾아보았다. (https://d2.naver.com/helloworld/0315536)
  • Tim sort, 현재 많은 언어들의 표준 정렬 알고리즘으로 사용되고 있다고 한다. Tim sort는 삽입정렬(Insertion Sort)와 합병정렬(Merge Sort)을 함께 적용한 정렬 기법이다.  (삽입정렬은 전형적으로는 O(N^2)의 시간복잡도를 가지지만 작은 배열을 정렬하거나, 이미 정렬된 부분이 많은 경우에 아주 좋은 성능을 보여준다.)
    • Tim sort는 전체 배열을 삽입정렬이 효율적으로 작동할 만큼의 단위로 분할하고 이 부분은 삽입정렬을 사용하여 기존 합병정렬 단계에 포함되는 병합 작업으로 발생하는 오버헤드를 최소화하였다. 또한 분할 단위를 넘더라도 정렬되어 있는 상태가 지속된다면 분할 단위에 포함시킴으로써 최적화시킨다. 즉, 삽입정렬을 효율적으로 사용함으로써 병합 단계 이전의 분할 덩어리들을 최대한 크게 만들어준다!
    • 삽입정렬을 오름차순으로만 적용하지 않고 새로운 분할 단위가 감소하며 진행된다면 내림차순 정렬을 사용한 후에 뒤집는 기법을 사용한다.
    • Tim sort의 삽입정렬은 Binary Insertion으로 삽입해야 할 위치를 찾는데 이분 탐색을 적용한다.
    • 이 외에도 메모리 효율을 높이기 위해 merge 방식에도 몇 가지 최적화 기법을 사용한다.
• 이제 왜 이런 결과가 나왔는지 이해가 된다.
  • sorted(arr1 + arr2)에서 이미 정렬되어 있는 두 배열을 이어 붙였기 때문에 Tim sort실행시 "분할 단위를 넘더라도 정렬되어 있는 상태가 지속된다면 분할 단위에 포함시킴으로써 최적화시킨다."에 따라 O(N + M)에 arr1, arr2로 다시 분할되고 이후의 작업은 동일하기 때문에 사실상 직접 구현한 방법과 동일하게 O(N + M)으로 정렬된다. (같은 작업이지만 내장함수는 C언어로 구현되어 있으니 더 빠른듯?) 

import sys
input = sys.stdin.readline

def solution(N, M, arr1, arr2):
    p1 = p2 = 0
    mergedArr = []

    while p1 < N and p2 < M:
        if arr1[p1] <= arr2[p2]:
            mergedArr.append(arr1[p1])
            p1 += 1
        else:
            mergedArr.append(arr2[p2])
            p2 += 1

    mergedArr += arr1[p1:] + arr2[p2:]
    mergedArr = ' '.join([str(e) for e in mergedArr])

    return mergedArr

if __name__ == '__main__':
    N, M = map(int, input().strip().split())
    arr1 = list(map(int, input().strip().split()))
    arr2 = list(map(int, input().strip().split()))
    result = solution(N, M, arr1, arr2)
    print(result)