[구현] (3-4) list 합치기: merge sort

문제 :  두 리스트 합치기

오름차순으로 정렬이 된 두 리스트가 주어지면 두 리스트를 오름차순으로 합쳐 출력하는 프로 그램을 작성하세요.

<입력설명>
첫 번째 줄에 첫 번째 리스트의 크기 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 리스트 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 리스트의 크기 M(1<=M<=100)이 주어집니다. 네 번째 줄에 M개의 리스트 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

<출력설명>
오름차순으로 정렬된 리스트를 출력합니다.

입력예제

3
1 3 5
5

2 3 6 7 9

출력예제

1 2 3 3 5 6 7 9

 

처음에는 뭐 이런 간단한 문제를 냈나 싶었다.

 

python에서는 그냥 + 연산자로 두 리스트를 합치고 sort하면 되지않는가?

 

import sys
input = sys.stdin.readline

N = int(input())
first_list = list(map(int, input().split()))
M = int(input())
second_list = list(map(int, input().split()))

combined_list = first_list + second_list
combined_list = sorted(combined_list)
for i in combined_list:
    print(i, end=" ")

 

물론 단순이 코딩테스트 합격을 위해서는 빠르고 쉬운 코딩이 정답이겠으나,

조금 더 효율적인 시간복잡도를 생각해보려고 했다.

 

현재 논리에서의 단점은 다음과 같다:  이미 각각 정렬되어있는 두 list를 다시 sort하는 것이 비효율적이다.

( O(N+M) + O( (N+M)ln(N+M) )

 

그래서 이전에 공부했던 merge sort의 방법을 차용하여 코드를 다시 생각해보기로 했다.

O(N+M)

 

def merge_sorted_lists(list1, list2):
    sorted_list = []
    i, j = 0, 0
    while i < len(list1) and j < len(list2):
        if list1[i] <= list2[j]:
            sorted_list.append(list1[i])
            i += 1
        else:
            sorted_list.append(list2[j])
            j += 1
    # 남은 요소들을 추가
    while i < len(list1):
        sorted_list.append(list1[i])
        i += 1
    while j < len(list2):
        sorted_list.append(list2[j])
        j += 1
    return sorted_list

# 병합 함수 호출
result = merge_sorted_lists(list1, list2)

# 결과 출력
print(''.join(map(str, result)))

 

gpt가 짜준 merge sort 코드인데, 일단 10분후에 스터디를 해야하므로 나중에 다시 탐구해보도록하지.