[실버 IV] 24060번. 알고리즘 수업 - 병합 정렬 1

 문제 

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

24060번: 알고리즘 수업 - 병합 정렬 1

 사용 언어 

Python3

 풀이 과정 

IDE에서는 정답이 출력되는 것을 확인했으나 채점이 느려서 불안한 순간 어김 없이 찾아온 시간 초과

import math
import sys

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

def mergeSort(array):
    if len(array) <= 1:
        return array # 최종 원소 하나짜리 배열
    mid = math.ceil(len(array)/2)
    # 재귀 사용
    first_array = mergeSort(array[:mid])
    second_array = mergeSort(array[mid:])

    return merge(first_array, second_array)

count = 0
def merge(arr1, arr2):
    result = []
    arr1_index = 0
    arr2_index = 0
    global N, K
    global count
    # 두 리스트 길이에 모두 도달하지 않았을 때
    while arr1_index < len(arr1) and arr2_index < len(arr2):
        if arr1[arr1_index] < arr2[arr2_index]:
            result.append(arr1[arr1_index])
            arr1_index += 1
        else:
            result.append(arr2[arr2_index])
            arr2_index += 1
        count += 1
        if count == K:
            print(result[-1])
    # 한 개의 리스트를 먼저 다 넣었을 때
    if arr1_index == len(arr1):
        while arr2_index != len(arr2):
            result.append(arr2[arr2_index])
            arr2_index += 1
            count += 1
            if count == K:
                print(result[-1])
    if arr2_index == len(arr2):
        while arr1_index != len(arr1):
            result.append(arr1[arr1_index])
            arr1_index += 1
            count += 1
            if count == K:
                print(result[-1])
    # N개를 다 합했지만 count가 K보다 작을 때
    if len(result) == N:
        if count < K:
            print(-1)

    return result

mergeSort(A)

내 생각엔 함수를 두 개 선언해서 merge함수가 호출될 때마다 global 변수들을 불러오는 게 일단 비효율적이어 보여서 두 함수를 합쳐줬다. 그리고 딱히 바꾼건 없는데 진짜 채점중이 2분정도 느~리~게 올라가더니 뜬 맞았습니다!!

메모리랑 시간 소비가 다른 문제들보단 높은데 정렬 문제라서 어쩔 수 없나 싶다. 다른 사람들이 블로그에 올린 것과 비교해보고 싶었는데 문제를 푼 사람이 별로 없더니 파이썬 코드는 찾을 수 없었다.

 제출 답안 

import math
import sys

N, K = map(int, sys.stdin.readline().strip().split(' '))
A = list(map(int, sys.stdin.readline().strip().split(' ')))
count = 0

def mergeSort(array):
    def merge(arr1, arr2):
        result = []
        arr1_index = 0
        arr2_index = 0
        global N, K, count
        # 두 리스트 길이에 모두 도달하지 않았을 때
        while arr1_index < len(arr1) and arr2_index < len(arr2):
            if arr1[arr1_index] < arr2[arr2_index]:
                result.append(arr1[arr1_index])
                arr1_index += 1
            else:
                result.append(arr2[arr2_index])
                arr2_index += 1
            count += 1
            if count == K:
                print(result[-1])
        # 한 개의 리스트를 먼저 다 넣었을 때
        if arr1_index == len(arr1):
            while arr2_index != len(arr2):
                result.append(arr2[arr2_index])
                arr2_index += 1
                count += 1
                if count == K:
                    print(result[-1])
        if arr2_index == len(arr2):
            while arr1_index != len(arr1):
                result.append(arr1[arr1_index])
                arr1_index += 1
                count += 1
                if count == K:
                    print(result[-1])
        # N개를 다 합했지만 count가 K보다 작을 때
        if len(result) == N:
            if count < K:
                print(-1)

        return result

    if len(array) <= 1:
        return array # 최종 원소 하나짜리 배열
    mid = math.ceil(len(array)/2)
    # 재귀 사용
    first_array = mergeSort(array[:mid])
    second_array = mergeSort(array[mid:])

    return merge(first_array, second_array)

mergeSort(A)

 공부한 내용 

병합 정렬(merge sort)

병합 정렬은 리스트를 반으로 나눠 왼쪽 정렬, 오른쪽 정렬한 것을 비교하여 다시 병합하는 정렬 방식이다.

따라서 전체 과정은 다음의 3단계로 구성된다.

• 분할(Divide) : 입력 배열을 절반 기준으로 2개의 부분 배열로 분할
• 정복(Conquer) : 부분 배열을 정렬, 부분 배열이 아직 덜 분할되었다면 재귀호출하여 분할 진행
• 결합(Combine) : 반환된 두 부분 배열을 하나의 배열로 병합

그리고 이러한 과정에 따라 아래와 같은 특성을 갖게 된다.

• 절반씩 나누는 과정에서 log n, 전체 정렬 과정에서 cn만큼 소요된다고 하면 정렬 알고리즘의 시간복잡도는 최선, 최악의 구분 없이 O(nlog n)이다.
• 추가 배열을 생성하여 병합하기 때문에 메모리 소모가 크다.
• 중복된 값이 있을 때 그 순서가 바뀌지 않는 안정된 정렬(Stable)이다.

이외 자세한 개념은 출처를 참고하도록 한다.

어쨌든 이러한 병합정렬은 보통 배열의 원소를 하나씩 뽑아서 새로운 배열에 더하는 방식으로 많이 설명되는데, 이러한 방법은 deque 자료형처럼 popleft를 지원하지 않으면 좌표 재배열*을 거치기 대문에 연산량이 (사실상 n^2로) 급격히 늘어난다. 따라서 배열이 아니라 좌표를 기준으로 표기해주면 연산량 문제가 해결되고, 내가 작성한 코드는 이러한 방식을 따른 것이다. 참고를 위해 아래 배열을 기준으로 병합한 코드를 추가한다.

* 좌표 재배열(relocate) : 맨 앞의 원소가 pop된 이후 나머지 원소들의 인덱스를 하나씩 줄여주는 것

def merge(list1, list2):
	merged = []
	while len(list1) > 0 and len(list2) > 0:
		if list1[0] <= list2[0]:
			merged.append(list1.pop(0))
		else:
			merged.append(list2.pop(0))

	if len(list1) > 0:
		merged += list1
	if len(list2) > 0:
		merged += list2

	return merged

 

출처: https://8iggy.tistory.com/120  | https://bblackscene21.tistory.com/8